https://vjudge.net/problem/UVA-11478
给定一个有向图，每条边都有一个权值。每次你可以选择一个结点v和一个整数d,把所有以v为终点的边的权值减小d,把所有以v为起点的边的权值增加d,最后让所有边的权值的最小值大于零且尽量大。
该死书上翻译错了 >0不是非负 WA好几次因为这个
考虑每条边的约束，di表示i的halum量
w-dv+du>0
dv-du<w
但求解这个差分约束系统只是让这组不等式成立，最长路和最短路控制的都是单个d的最值而不是最小值最大
那如何最小值最大呢？
二分答案......
那么不等式变为dv-du<w-mid，成立的话说明经过操作后边权可以都比mid大
无解的话就是mid=1,*的话就是mid=最大边权(不能用1e9，溢出)的时候也成立
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=,M=,INF=1e9;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m,u,v,w;
struct edge{
int v,ne;
double w;
}e[M];
int h[N],cnt=;
inline void ins(int u,int v,int w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
}
int q[N],head,tail,inq[N],num[N],d[N];
inline void lop(int &x){if(x==N) x=;else if(x==) x=N-;}
bool spfa(int mid){
head=tail=;
memset(inq,,sizeof(inq));
memset(num,,sizeof(num));
for(int i=;i<=n;i++) q[tail++]=i,inq[i]=,d[i]=;
while(head!=tail){
int u=q[head++];inq[u]=;lop(head);
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w-mid;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
if(!inq[v]){
inq[v]=;
if(++num[v]>n) return true;
if(d[v]<d[q[head]]) head--,lop(head),q[head]=v;
else q[tail++]=v,lop(tail);
}
}
}
}
return false;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
cnt=;memset(h,,sizeof(h));
int l=,r=,ans=;
for(int i=;i<=m;i++) u=read(),v=read(),w=read(),ins(u,v,w),r=max(r,w);
if(spfa(l)){puts("No Solution");continue;}
else if(!spfa(r)){puts("Infinite");continue;}
else{
while(l<=r){
int mid=(l+r)>>;
if(!spfa(mid)) ans=mid,l=mid+;
else r=mid-;
}
printf("%d\n",ans);
}
}
}