又是类似食物链的这一类题
这题是找与根节点的和差关系 因为0节点是已知的 为0 那么所有的都可以转换为与0的和差关系
可以规定合并的两节点 由大的指向小的 然后再更新和差关系
有可能最后有的不在0集合中 这时要确定最大初值 当然根据集合中出现的负值来确定 题目中工资不能出现负值 也不可大于10^9 在处理完关系后 再判断一下这两个条件 不满足的话就输出m
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
#define N 50010
#define LL long long
#define maxz 1000000000
int n,m;
int f[N];
LL r[N],mm[N];
int find(int x)
{
if(x!=f[x])
{
int o = f[x];
f[x] = find(f[x]);
r[x] += r[o];
}
return f[x];
}
int main()
{
int i,a,b,c;
int flag = ,tx = maxz;
scanf("%d%d",&n,&m);
for(i = ; i < n ; i++)
{
f[i] = i;
r[i] = ;
}
for(i = ;i <= m ; i++)
{
scanf("%d%d%d",&a,&b,&c);
if(flag)
continue;
int x = find(a),y = find(b);
if(x!=y)
{
if(x<y)
{
swap(x,y);
swap(a,b);
c = -c;
}
f[x] = y;
r[x] = -r[a]+r[b]+c;
}
else
{
if(r[a]-r[b]!=c)
{
flag = ;
tx = i; }
}
}
for(i = ; i < n ; i++)
{
int ho = find(i);
if(ho!=)
{
if(r[i]<)
{
mm[ho] = max(mm[ho],-r[i]);
}
}
}
for(i = ; i < n ; i++)
{
int ff = find(i);
if((r[i]+mm[ff])>maxz||(r[i]+mm[ff])<)
{
flag = ;
tx = m;
break;
}
}
if(flag)
{
printf("Impossible after %d statements\n",tx);
return ;
}
puts("Possible");
printf("0\n");
for(i = ; i < n ; i++)
{
int ff = find(i);
printf("%lld\n",r[i]+mm[ff]);
}
return ;
}