题：https://codeforces.com/contest/1450/problem/E
题意：给定n点m边图，边：[u,v,d]当d为1时，a[v]-a[u]=1，当d为0时，|a[v]-a[u]|=0，求给a数组赋值，图关系合法且最大化max{ a[i] } - min{ a[i] }
分析:
- 差分约束”=“的情况，将d==1时的情况转化为a[v]-a[u]<=1, a[v]-a[u]>=1，所以cost[u][v]=1,cost[v][u]=-1。
- 同理，d==0时cost[u][v]=1,cost[v][u]=1, 求差值最大根据差分约束去跑最短路；
- ”NO“情况就判断有无负权环和判断路径是否合法，
#include<bits/stdc++.h> using namespace std; #define pb push_back #define MP make_pair #define UM unordered_map typedef long long ll; const int mod=1e9+7; const int inf=0x3f3f3f3f; const ll INF=1e18; #define pi 3.1415926535898 #define DEC (pi/180) const int M=202; int cost[M][M]; int u[M*10],v[M*10],d[M*10]; void py(){ puts("YES"); } void pn(){ puts("NO"); } int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) cost[i][j]=inf; for(int i=1;i<=m;i++){ scanf("%d%d%d",&u[i],&v[i],&d[i]); cost[u[i]][v[i]]=1; cost[v[i]][u[i]]=(d[i] == 1 ? -1 : 1); } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]); } } ///negative for(int i=1;i<=n;i++) if(cost[i][i]<0) return pn(),0; ///find max int pos=1,maxx=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(maxx<cost[i][j]){ maxx=cost[i][j]; pos=i; } ///judge legal for(int i=1;i<=m;i++) if(cost[pos][u[i]]==cost[pos][v[i]]) return pn(),0; py(); printf("%d\n",maxx); for(int i=1;i<=n;i++) printf("%d ",cost[pos][i]); return 0; }