最小割

有某位神仙说过,一切问题都是网络流.很多涉及到代价,贡献,依赖,互斥的问题都可以转化为最小割来处理.一般不会给出明显的图关系,很多时候需要根据图中信息建立隐式图.推荐两篇论文,hbt的《最小割模型在信息学竞赛中的应用》和pty的《浅析一类最小割问题》,透彻明晰的分析了几个最常用模型.

基本思路

考虑最基本的只有一个非源汇节点的网络,最小割的结果就是源汇边容量的较小者.如果有两个非源汇节点链式相连,最小割的结果等于三条边容量的最小值.将中间的边容量设为无穷,则可表现两个点互斥,即必须二选一的限制.

如果中间的边容量有意义,那么他代表选取前者而放弃后者的代价.只有这条边流满,顶点才能分属不同点集.

对于依赖关系,可以考虑类似于否定否命题的思路构造.将任一非源汇点按出边入边拆为出点入点,可以代表选与不选,则两点互斥,依赖入点等价于与出点互斥.在某些情况下,入点和出点的区别并不会直接影响图的性质,就可以将两个点合并,此时目标点直接向依赖点连容量无限的边.也可以用代价的观点看成选后者而不选前者的代价无穷大,两者必须归属同一划分.

在原图解最小割的结果就是满足限制的最小代价.如果要求最大收益,一般预先将价值求和,再减去最小割.

小M的作物

https://www.luogu.com.cn/problem/P1361
题意:有n种作物,每一种可以种在A,B两个田里,分别收获$a_i,b_i$的价值.给出m种组合,若组合内所有作物都种在A,B内,额外获得$ea_i,eb_i$的价值.求出可以获得的最大价值.

首先不看额外附加的价值,直接贪心就是答案.贪心策略毫无疑问就是选取较大者,也可以转述为两者之和减去较小者.~~很容易联想到~~,最小割也可以用来求两者中的较小值.将权值作为容量,分别连向源汇,达到满流后,总流量就是二者中的较小者.最大价值可以预先存下所有价值的和,再减去最小割得到.

那么这个直接能无脑贪心的问题,为什么要去扯上最小割呢?最小割可以处理依赖关系下的求值,刚好能解决组合额外价值的计算.考虑将每种作物拆分为A,B两个点,分别代表选择田地A或B,再将组合建立虚拟点,可以发现图中的依赖关系,任一个组合能被选取仅当所有目标作物都选为对应的土地,即$ma_i$依赖于$a_j,(j \in {S_i})$全部被选取.

此处并不需要直接把代表作物的点拆出来,因为入点和出点之间的边容量为无穷,合并也不会影响结果.黑边的容量为无限.在最小割中,以代价或贡献的角度考虑,无限容量代表永远不割去此条边,即不选择依赖项直接选则目的项的代价无限大.这样就可以保证,要么不选此项,割掉其与源汇点的边,要么捆绑式选取所有依赖点.

求额外价值的方法和单个点一样,预先将价值加到总和中,最后减去最小割.

For(i,1,n)cin>>rec[i][0],sum+=rec[i][0];
For(i,1,n)cin>>rec[i][1],sum+=rec[i][1];
For(i,1,n)con(S,i,rec[i][0]),con(i,T,rec[i][1]);
For(i,1,m){
    con(S,p1,v1),con(p2,T,v2),sum+=v1+v2;
    For(j,1,k){ll p;cin>>p;con(p1,p,INF),con(p,p2,INF);}
}
dinic();
cout<<sum-mxf;

city safety

https://codeforces.com/gym/103428/problem/H
题意：一棵树，加强第i 个点有$w_i$ 的花费，而如果距离某个点≤ d 的所有点都加强了，则会有$v_d$ 的收益，求最大净收益。
看起来像个树形dp,但是祖先的状态不好处理,转移方程写不出~~太菜了~~.于是考虑歪门邪道.

将贡献差分,将每个点处的贡献拆为n个点,建图,可以发现这是一个典型的依赖-代价图.于是考虑分别找出依赖关系和正负收益建图.
每个点都做一次dfs得到依赖关系,距离点p为d的贡献所对应的点依赖于距离点p为d-1的对应点,和原树中距离树节点p为d的所有树节点.对于所有依赖关系连上容量无限的单边.
源点向所有代表贡献的点连上容量为贡献差分的边,所有树节点向汇点连上容量为代价的边,就是最小割的经典模型.
预先对所有贡献求和,最后的结果就是总和减去最小割.

void dfs2(int p,int d,int f,int S){
    con(S+n*d,p,INF);
    For(i,0,od2[p]-1){
        if(ov2[p][i]^f)dfs2(ov2[p][i],d+1,p,S);
    }
}
void solve(){
    For(i,1,n){ll v;cin>>v;con(i,T,v);}
    ll pre=0;
    sum=n*bnf[n];
    For(i,1,n){
        dfs2(i,1,0,i);
        For(j,1,n){con(S,i+j*n,bnf[j]-bnf[j-1]);if(j>1)con(i+j*n,i+j*n-	n,INF);}
    }
    dinic();
    cout<<sum-mxf;
}

土地划分

https://www.luogu.com.cn/problem/P4210
题意:在一张无向联通图中,每个点归属点集1,点集n二者之一,分别获得$a_i,b_i$的收益.如果一条边两个顶点同属于点集1或点集n,则额外获得$Ea_i,Eb_i$的收益,若一条边两个顶点不属于同一点集,则会产生$Ec_i$的损失.求一种划分使得收益最大.

这个模型太眼熟了,可以用pty论文中的方法解决.
简单回顾一下模型,~~知道的大佬可以直接跳过~~

机械调度

有n个任务,每个可以在机械A,B上完成,所选的方案记为二元组$(x,y)$.选择A或B会产生$A_i,B_i$的代价.对于每一组$(x,y)$,都会产生一组给定的代价,$v_1,v_2,v_3,v_4$.求一种方案使得总代价最小.

对于每个任务的代价,暂不考虑,可以最后再加到割边上去.现考虑二元组的影响,在原图上重新建边.

边的容量必须满足以下限制

$a+b=v1 \\ c+d=v2 \\ a+e+d=v3 \\ b+f+c=v4$

其中可能出现类似$a+b+d$的方案,因为肯定不如$a+b$优,不用考虑.
在这个图中,点x,y具有类似于对称的性质,所以e,f可以直接取等,$e=f=(v3+v4-v1-v2)/2$.剩下的容量也可以直接怎么简单取,任何一种合法的选取最后并不影响答案的正确性.

$a=(v1+v3)/2 \\ b=(v1-v3)/2 \\ c=(v2+v4)/2 \\ d=(v2-v4)/2 \\ e=f=(v3+v4-v1-v2)/2$

然后以每个任务自身的代价连边,最后最小割就是答案.

回到本题,将所有的代价取负变为贡献,答案就是所有容量的和减去最小割.
与模型唯一的不同就是划分不同时的代价变成了贡献,那就预先把所有的贡献加和,再将容量的差加到相同划分的代价上,最后如果划分不同时结果会相抵消.

For(i,2,n-1){ll v;cin>>v;v*=2,sum+=v,con(S,i,v);}
For(i,2,n-1){ll v;cin>>v;v*=2,sum+=v,con(i,T,v);}
For(i,1,m){
    int p1,p2;ll v1,v2,v3;
    cin>>p1>>p2>>v1>>v2>>v3;
    sub+=v3,v1+=v3,v2+=v3;
    v1*=2,v2*=2,sum+=v1+v2;
    con(S,p1,v1/2);
    con(S,p2,v1/2);
    con(p1,T,v2/2);
    con(p2,T,v2/2);
    con(p1,p2,(v1+v2)/2);
    con(p2,p1,(v1+v2)/2);
}

方格取数问题

https://www.luogu.com.cn/problem/P2774
题意:给定一个n*m的矩阵,要求取出若干个数,使总和最大,同时满足每个数在矩阵中的位置都不相邻

相邻不能同时取,这个条件给出了互斥性,暗示着可以根据矩阵中位置的奇偶性,将原图看作一张二分图,不相交的两侧分别代表奇偶点,代表两个点至少一条连向源汇的边被割掉,即至少弃掉一个点.原问题等价于二分图带权最大独立集.

这个总和最大感觉不太好求,就转化问题,求一个取数组合使剩下的数均不相邻,且该组合最小.这种取法会将原二分图拆成两个不相连部分,与最大流的残量网络极其相像.最后的S,T集里的点就是目标取点.

~~图中黑边为被删去的边,蓝边为可行边~~此图有误,被删去的边可能流量在残量网络没有跑完,但经过调整后一定可以使每条边对应点的状态.

圈地计划

https://www.luogu.com.cn/problem/P1935
题意:一个nm矩阵,每个点位选择A或B,得到收益$a_{ij},b_{ij}$.若两个相邻的点选择不同,获得额外收益$C_{ij}+C_{kl}$.求所能获得的最大收益.

很显然,pty的模型可以直接套用,不过此处由于图的结构,需要做一些变换.此处用更好理解的虚拟点法,同时进行了和论文中变换本质相同的构造.

这是个有互斥属性的矩形问题,不妨想想方格取数中的解决方案,按奇偶来分类点.将所有的奇点反转,入点和出点交换,源汇边容量交换,就重新得到一张意义明确的类二分图.再按对相邻的依赖关系对虚拟店连边,就可以求出正确的最小割.

For(i,1,n)For(j,1,m){ll v;cin>>v;sum+=v;if((i+j)&1)con(S,p,v);else con(p,T,v);}
For(i,1,n)For(j,1,m){ll v;cin>>v;sum+=v;if((i+j)&1)con(p,T,v);else con(S,p,v);}
For(i,1,n)For(j,1,m){
    ll v;cin>>v;
    if(i^1)sum+=v,con(S,eg,v),con(eg,p,INF),con(eg,x,INF);
    if(i^n)sum+=v,con(S,eg,v),con(eg,p,INF),con(eg,x,INF);
    if(j^1)sum+=v,con(S,eg,v),con(eg,p,INF),con(eg,x,INF);
    if(j^m)sum+=v,con(S,eg,v),con(eg,p,INF),con(eg,x,INF);
}

人员雇佣

https://www.luogu.com.cn/problem/P1791
题意:有n个员工,雇佣成本分别为$a_i$.若$i,j$两个员工同时雇佣,则获得收益$E_{i,j}$,如果其中一人被雇佣而另一人没有,则付出额外代价$E_{i,j}$.求最大收益.

用虚拟点的想法,拆点为选或不选,再将额外收益或惩罚连依赖边,最后再处理收益与惩罚的互斥性上遇到了麻烦,似乎并不好表示.

考虑边的意义.先将贡献加和转化问题为求最小代价,向源汇连收益和代价.点i向点j连容量为$2E_{i,j}$的边,表示两者不在同一集合的代价为$2E_{i,j}$,就搞定辣.

For(i,1,n){ll v;cin>>v;con(i,T,v);}
For(i,1,n)For(j,1,n){
    ll v;cin>>v;if(i==j)continue;
    rec[j]+=v,sum+=v,con(i,j,v*2);
}
For(i,1,n)con(S,i,rec[i]);

Nebulyu's Blog

最小割练习

最小割