Bakser's Blog

我是逗比。

bzoj1202加权并查集

| Comments

好多题解不说了。

bzoj1202
#include<cstdio>
#include<cstring>
using namespace std;
#define N 120
int fa[N],T,n,m,dis[N];
inline int find(int x)
{
    if(!fa[x])return x;
    int tmp(find(fa[x]));
    dis[x]+=dis[fa[x]];
    return fa[x]=tmp;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(fa,0,sizeof(fa));
        memset(dis,0,sizeof(dis));
        bool flag=0;
        scanf("%d%d",&n,&m);
        for(int i(0),s,t,w;i<m;i++)
        {
            scanf("%d%d%d",&s,&t,&w);
            if(flag)continue;
            int p(find(s));
            int q(find(++t));
            if(p!=q)fa[q]=p,dis[q]=dis[s]+w-dis[t];
            else if(dis[t]-dis[s]!=w)flag=1;
        }
        puts(flag?"false":"true");
    }
    return 0;
}

Comments

comments powered by Disqus