逆向考虑 枚举每一天 看这一天是否有桥断掉 断掉是否影响联通即可
#include <bits/stdc++.h> using namespace std; struct node { int u; int v; int t; }; node edge[100010]; int f[10010]; int n,m; bool cmp(node n1,node n2) { return n1.t>n2.t; } int getf(int p) { if(f[p]==p) return p; else { f[p]=getf(f[p]); return f[p]; } } bool unite(int u,int v) { int fu,fv; fu=getf(u); fv=getf(v); if(fu!=fv) { f[fv]=fu; return true; } else return false; } int main() { int i,j,pre,ans,flag; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=m;i++) { scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].t); } sort(edge+1,edge+m+1,cmp); for(i=1;i<=n;i++) { f[i]=i; } pre=1,ans=0; for(i=100000;i>=1;i--) { flag=0; for(j=pre;j<=m;j++) { if(edge[j].t!=i) break; if(unite(edge[j].u,edge[j].v)) { flag=1; } } pre=j,ans+=flag; } printf("%d\n",ans); } return 0; }
