简介：

带权有向图，每个点都可以有如下操作：令从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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=1010;int n,m;struct node{ int x,y,v;};struct Bellman{ int n,m; vector
           
             e; vector
            
              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
             
               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
              
               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