原文链接https://www.cnblogs.com/zhouzhendong/p/AtCoder-SoundHound-Inc-Programming-Contest-2018-E.html
题目传送门 - AtCoder SoundHound Inc. Programming Contest 2018 E
题意
给定一个无向连通图，有 $n$ 个节点 $m$ 条带权边，第 $i$ 条边连接 $x_i,y_i$ ，权值为 $s_i$ ，没有重边、自环。
现在，请你给每一个节点取一个正整数点权。问有多少种方案使得任意一条边两端的节点权值和等于边权。
$2\leq n\leq 100000,1\leq m\leq 100000$
所有输入的数字都在 $10^9$ 以内。
题解
先吐槽：
这题细节好坑啊！！！我当场做到只 WA 一个点，没想到 20 分钟还是没有发现特判，然后 GG 。然后考完发现在我没注意的地方忘记特判了？？然后考完不到10分钟把它过了。就加了几行。
然后讲做法。
设 $v_i$ 为第 $i$ 个点的点权。
首先，我们考虑到对于所有的 $i$ ，有 $v_{x_i}+v_{y_i}=s_i$ 。我们把式子移动一下，得到：
$$v_{x_i}-s_i=(-v_{y_i})$$
$$(-v_{y_i})+s_i=v_{x_i}$$
$$v_{y_i}-s_i=(-v_{x_i})$$
$$(-v_{x_i})+s_i=v_{y_i}$$
我们使节点 $1$ 作为初始节点，即令 $v_1=\alpha$ 。
我们考虑将每一个点拆成两个点，一个点记录其正的权值（即 $v_i=\alpha + k$ 时，记录的值为 $k$ ），另一个点记录其负权值（即 $-v_i=\alpha+k$ ，记录的值为 $k$）。
然后我们对于每一条边，拆成上述四条有向边。
然后 bfs 一遍把每一个点与 $\alpha$ 的关系求出来。这里注意一点，如果到达一个点有两条距离不同的路径，那么显然答案为 $0$ 。（条件冲突）
然后我们得到了一些数据。
我们考虑去解决那些拆点之后两个节点都被访问的节点。
对于每一个这样的节点，我们可以解出唯一的 $\alpha$ ，如果所有节点的解有不同，那么答案显然是 $0$ 。否则答案显然是 $1$ 。
请您先思索一下在选中下面黑色矩形区域内的字看下面的话。
这样是错的！！我就是挂在这里了。我们不能这么着急的确定答案是 $1$ 。因为我们还需要满足所有点权均为正整数。所以我们还需要判一判。
然后就只剩下二分图的情况了。
对于这种情况，我们只需要根据每一个节点与初始节点 $1$ 的关系，根据“正整数”这个条件更新 $\alpha$ 的取值范围。最后输出即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=400005;
struct Gragh{
int cnt,y[N],z[N],nxt[N],fst[N];
void clear(){
cnt=0;
memset(fst,0,sizeof fst);
}
void add(int a,int b,int c){
y[++cnt]=b,z[cnt]=c,nxt[cnt]=fst[a],fst[a]=cnt;
}
}g;
int n,m;
int q[N],head,tail;
LL dis[N];
LL INF=10000000000000000LL;
void out0(){
puts("0");
exit(0);
}
void SPFA(int S){
for (int i=1;i<=n*2;i++)
dis[i]=INF;
head=tail=0;
q[++tail]=S;
dis[S]=0;
while (head!=tail){
int x=q[++head],y;
for (int i=g.fst[x];i;i=g.nxt[i]){
int y=g.y[i];
if (dis[y]!=dis[x]+g.z[i]){
if (dis[y]!=INF)
out0();
dis[y]=dis[x]+g.z[i];
q[++tail]=y;
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
g.clear();
for (int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g.add(a,b+n,-c);
g.add(b+n,a,c);
g.add(b,a+n,-c);
g.add(a+n,b,c);
}
SPFA(1);
LL v=INF;
for (int i=1;i<=n;i++)
if (dis[i]!=INF&&dis[i+n]!=INF){
LL A=dis[i],B=dis[i+n];
if ((A+B)%2LL)
out0();
LL x=-(A+B)/2LL;
if (x!=v)
if (v==INF)
v=x;
else
out0();
}
if (v!=INF){
int f=1;
for (int i=1;i<=n;i++){
if (dis[i]!=INF)
if (v+dis[i]<=0)
f=0;
if (dis[i+n]!=INF)
if (v+dis[i+n]>=0)
f=0;
}
printf("%d",f);
return 0;
}
LL MIN=1,MAX=INF;
for (int i=1;i<=n;i++)
if (dis[i]!=INF)
MIN=max(MIN,-dis[i]+1);
else
MAX=min(MAX,-dis[i+n]-1);
printf("%lld",max(MAX-MIN+1,0LL));
return 0;
}