HDU3047 Zjnu Stadium 带权并查集

转:http://blog.csdn.net/shuangde800/article/details/7983965

#include <cstdio>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int N=2e5+;
int n,m,fa[N],sum[N];
int find(int x)
{
if(x==fa[x])return fa[x];
int t=fa[x];
fa[x]=find(fa[x]);
sum[x]+=sum[t];
return fa[x];
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=; i<=n; ++i)fa[i]=i,sum[i]=;
int ans=;
while(m--)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
int x=find(u),y=find(v);
if(x==y)
{
if(sum[v]-sum[u]!=w)++ans;
}
else if(x>y)
{
sum[x]=sum[v]-sum[u]-w;
fa[x]=y;
}
else
{
sum[y]=sum[u]-sum[v]+w;
fa[y]=x;
}
}
printf("%d\n",ans);
}
return ;
}
上一篇:javascript性能优化-repaint和reflow


下一篇:python(51):Python vars() 函数