Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3726 Accepted Submission(s): 1415
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<map> #include<queue> #include<stack> #include<vector> #include<set> using namespace std; #define PI acos(-1.0) typedef long long ll; typedef pair<int,int> P; const int maxn=1e5+100,maxm=1e5+100,inf=0x3f3f3f3f,mod=1e9+7; const ll INF=1e13+7; int pa[maxn]; int dist[maxn]; void init(int n) { for(int i=1; i<=n; i++) pa[i]=i,dist[i]=0; } int findset(int x) { if(pa[x]==x) return x; int fax=pa[x]; pa[x]=findset(pa[x]); dist[x]+=dist[fax]; return pa[x]; } void unit(int x,int y,int w) { int fx=findset(x),fy=findset(y); pa[fx]=fy; dist[fx]=dist[y]+w-dist[x]; } bool same(int x,int y,int w) { if(findset(x)!=findset(y)) return false; else if(dist[findset(x)]==dist[y]+w-dist[x]) return false; else return true; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { int ans=0; init(n); for(int i=1; i<=m; i++) { int a,b,x; scanf("%d%d%d",&a,&b,&x); if(same(a,b,x)) ans++; else unit(a,b,x); } cout<<ans<<endl; } return 0; }
原文:http://www.cnblogs.com/GeekZRF/p/7113263.html