4 4
1 2 2
1 3 2
2 3 1
3 4 3
2
分析：
按t由大到小排序 ， 然后遍历一遍边m ， 一遍遍历m一边用并查集判断边的两端是否是连通,如果不连通同时不与前面的时间天数相等着答案加+ ， 同时路径压缩
现在分析为什么这样做：首先我们肯定知道t数越大越可以活在最后 ， 前的边的天数是不可抵消掉大的天数的边所以如果我们逆向来考虑的话 ， 大天数的连通了 ， 在遍历下去连通性不会改变
不了解看着
#include<bits/stdc++.h> using namespace std ; struct no { int a,b,t; }G[100001]; int fa[10001]; bool cmp(no a , no b) { return a.t>b.t; } int find(int u) { if(u==fa[u]) return u; return fa[u]=find(fa[u]); } bool joint(int a , int b) { int x=find(a); int y=find(b); if(x==y) ///连通 return false; if(x!=y) fa[x]=y; return true; } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1 ; i<=m ; i++) { scanf("%d%d%d",&G[i].a , &G[i].b , &G[i].t); } for(int i=1 ; i<=n ; i++) fa[i]=i; sort(G+1,G+1+m,cmp); int ans = 0; int pretime=-1; for(int i=1 ; i<=m ; i++) { if(joint(G[i].a , G[i].b) && G[i].t!=pretime) ///a , b 两端不连通 ， 且不等于上位大时间 { ans++; pretime=G[i].t; } } printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/shuaihui520/p/10452808.html