简介：
带权有向图，每个点都可以有如下操作：令从ta出发的每一条边增加d，终止于ta的每一条边减小d
最后让所有边权的最小值非负且尽量大
分析：
我为什么总是要做这么难的题
有一点需要注意，不同的操作互不影响，而且也没有顺序的限制，
因此，我们可以考虑合并一个节点上的所有操作
令sum（a）表示作用在a结点上的所有d值之和，
这样我们就简化了题目：找到合适的sum值，使得所有边权最小值最大。
最小值最大，这个描述这么这样熟悉
我们一下子就想到了二分答案
最直接的，我们可以直接二分出最小边权
然而，二分的难点不在于“二分出答案”，而是“判断答案的合法性”
对于一个答案mid
问题转化成判断是否可以通过确定一个合法的sum，使得每条边的权值都大于等于mid
任何一条边（a—>b）的实际权值为w(a,b)+sum(a)-sum(b)
显然我们可以得到一个柿子：w(a,b)+sum(a)-sum(b)>=mid
移项得：sum(b)-sum(a)<=w(a,b)-mid
这样实际上我们得到一个差分约束系统
差分约束
即一个不等式组，每个不等式形如xj-xi<=bk
针对这一问题，有一个经典的解法：最短路
我们可以移项得到xj<=bk+xi
这样柿子的形式就和最短路的形式有异曲同工之妙了
dis表示源点到达每一个结点的最短路
对于每一条边（i—>j）,都有dis[j]<=dis[i]+w(i,j)
这样我们对于每一个约束条件xj-xi<=bk
都连一条i—>j的边，权值为bk
再建立一个超级源点S，连向每一个点，边权为0
在这个图上运行Bellman，得到的dis就是sum数组
如果Bellman失败（存在负环），则该差分约束系统无解
我们在实际编码的时候，实际上就是把原图建出来，
每二分一个答案，就把每条边的权值相应的改变，运行Bellman
tip
题目说最小值非负，但是代码中最小值应该是>=1
也许在歪果人眼里0是负数，mdzz
这道题给了我们很好地启发：
- 操作叠加
如果若干操作互不干扰，无序施加，我们就可以考虑合并这些操作，这样方便思考也方便处理 - 模型抽象
我们需要记住这个模型：形如xj-xi<=b，建边i->j，边权为b
（若得到的模型为xi-xj>=b，变形后xj-xi<=-b => 建边i->j，边权为-b）
运行Bellman，判断该差分约束是否有解
关于差分约束的详细内容，会在再谈最短路中提及
//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=1010;
int n,m;
struct node{
int x,y,v;
};
struct Bellman{
int n,m;
vector<node> e;
vector<int> G[N];
bool in[N];
int cnt[N];
int dis[N];
int pre[N];
void init(int n)
{
this->n=n;
e.clear();
for (int i=1;i<=n;i++) G[i].clear();
}
void add(int u,int w,int v)
{
e.push_back((node){u,w,v});
m=e.size();
G[u].push_back(m-1);
}
bool fuhuan()
{
memset(in,0,sizeof(in));
memset(pre,0,sizeof(pre));
memset(cnt,0,sizeof(cnt));
queue<int> Q;
for (int i=1;i<=n;i++) //建立了一个虚拟源点，所以与ta相连的点都入队
{
in[i]=1;
Q.push(i);
dis[i]=0;
}
while (!Q.empty())
{
int now=Q.front();
Q.pop();
in[now]=0;
for (int i=0;i<G[now].size();i++)
{
node way=e[G[now][i]];
if (dis[way.y]>dis[now]+way.v)
{
dis[way.y]=dis[now]+way.v;
pre[way.y]=G[now][i];
if (!in[way.y])
{
in[way.y]=1;
Q.push(way.y);
if (++cnt[way.y]>n) return 1;
}
}
}
}
return 0;
}
};
Bellman A;
bool pd(int x)
{
for (int i=0;i<A.m;i++)
A.e[i].v-=x;
bool pp=A.fuhuan();
for (int i=0;i<A.m;i++)
A.e[i].v+=x;
return pp;
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
A.init(n);
int maxx=0;
for (int i=1;i<=m;i++)
{
int u,w,z;
scanf("%d%d%d",&u,&w,&z);
A.add(u,w,z);
maxx=max(maxx,z);
}
if (!pd(maxx+1)) printf("Infinite
");
//不存在环，也就是说答案再大都是可以的
else if (pd(1)) printf("No Solution
"); //下边界
else
{
int l=0; //
int r=maxx;
int mid,ans;
while (l<=r)
{
mid=l+(r-l)/2;
if (!pd(mid)) //不存在负环,说明有解
ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d
",ans);
}
}
return 0;
}