题目链接：http://vjudge.net/contest/143318#problem/B
题意：给定一个有向图，每条边都有一个权值。每次你可以选择一个结点v和一个整数d,把所有以v为终点的边的权值减小d,把所有以v为起点的边的权值增加d,最后让所有边的权值的最小值大于零且尽量大。
分析:
最小值尽量大，二分，最大不能超过最大边，要是最大边的话，其他边满足不了非负；
题意说的各种操作，他互不影响；也就变成了操作各边。
对于各点的操作来说：
令sum(u) 是作用于 u 上的所有 d 之和;
a—> b边的权值就是： w(a,b) +sum(a) - sum(b)>=x(答案);
对上式 变形： sum(b) - sum(a) <= w(a,b) -x;
sum(b) - sum(a) 就是对这条边的操作。
这就是一个差分约束系统。
枚举这个sum(b) - sum(a) ，要是有负环，就是查分系统无解。
没有负环，说明，这个最小值还可以大一点。
#include <bits/stdc++.h>
using namespace std; const int maxn = + ; struct Edge
{
int from,to;
double dist;
}; struct BellmanFord
{
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];
double d[maxn];
int p[maxn];
int cnt[maxn]; void init(int n)
{
this->n = n;
for(int i = ; i < n; i++) G[i].clear();
edges.clear();
} void AddEdge(int from, int to, double dist)
{
edges.push_back((Edge)
{
from, to, dist
});
m = edges.size();
G[from].push_back(m-);
} bool negativeCycle()
{
queue<int> Q;
memset(inq, , sizeof(inq));
memset(cnt, , sizeof(cnt));
for(int i = ; i < n; i++)
{
d[i] = ;
inq[] = true;
Q.push(i);
} while(!Q.empty())
{
int u = Q.front();
Q.pop();
inq[u] = false;
for(int i = ; i < G[u].size(); i++)
{
Edge& e = edges[G[u][i]];
if(d[e.to] > d[u] + e.dist)
{
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
if(!inq[e.to])
{
Q.push(e.to);
inq[e.to] = true;
if(++cnt[e.to] > n) return true;
}
}
}
}
return false;
}
}; BellmanFord solver; bool test(int x)
{
for(int i=; i<solver.m; i++)
{
solver.edges[i].dist -=x;
}
bool ret = solver.negativeCycle();
for(int i=; i<solver.m; i++)
{
solver.edges[i].dist +=x;
}
return !ret;
} int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{ solver.init(n);
int ub = ; for(int i=; i<m; i++)
{
int u,v,dist;
scanf("%d%d%d",&u,&v,&dist);
ub = max(ub,dist);
u--;
v--;
solver.AddEdge(u,v,dist);
} if(test(ub+)) puts("Infinite");
else if(!test()) puts("No Solution");
else
{
int L = , R = ub, ans = ;
while(L <= R)
{
int M = L + (R-L)/;
if(test(M)) //没有负环
{
ans = M;
L = M+;
}
else R = M-;
}
printf("%d\n", ans);
}
}
return ;
}