最大流练习

最大流

飞行员配对问题

https://www.luogu.com.cn/problem/P2756
网络流24题里的入门一题.
两种人之内没有交集,整个图可以看作二分图,跑匈牙利算法
也可以根据每个外籍飞行员和英国飞行员之间配对关系连边,看作最大流
在图中额外加入源点和汇点,分别与两组点连边,最大流的结果就是所求匹配数
最后输出方案就直接扫描残量网络,若起于外国并终于英国的边被流过则说明这两个人配对

For(p,1,n1){
        For(i,0,od[p]-1){
            if(e.f||e.t<=n1) continue;
            cout<<p<<" "<<e.t<<"\n";break;
        }
    }

试题库问题

https://www.luogu.com.cn/problem/P2763
每一题仍然只能选取一次,但每张卷子都要求多道题
将与源点连边的容量改为题数,判断最大流是否等于总题数
输出方案时同上题做法

圆桌问题

https://www.luogu.com.cn/problem/P3254
试题库问题的升级版,每组点都有多种限流
将汇点连边的容量也改为要求就行了

魔术球问题

https://www.luogu.com.cn/problem/P2765
题意:有n个柱子,每个柱子上可以放球,相邻的球必须满足编号和为完全平方数,最大化放球的数量

这一题并没有直接的给出建图的信息,需要从相邻编号和为平方的限制条件中得到球之间的合法转移关系,就可以依此建出隐式图.

匹配数+柱子个数=球个数,所以我们不断试图增加匹配,在残量网络上不断跑最大流,直到匹配的最大值,就可以使球的个数最多.如果加入一个点而无法使匹配增大,那么说明球的个数已经达到了最大值.

如果沿用之前直接基于每个球代表的编号点进行转移的思路,源点流出的流量可以经过中转点直接流向汇点,起不到寻找匹配的作用.这里就需要拆点,用两个点代表一个球,分别与源汇点相连,入点连向可以组成平方数的出点,每次最大流的结果就是匹配数.

最后记得每次保存增加点之前的边,如果到达上限就清空并还原残量网络,最后一次跑最大流就可以得到点之间的匹配关系

while(1){
    ++add;lim+=2;int totrec=tot;
    ins(S,lim-1,1),ins(lim,T,1);
    For(i,1,n+add-1)if(check(i,n+add)) ins(2+i*2-1,lim,1);
    dinic();if(add==mxf) continue;
    lim-=2,tot=totrec;break;
}
for(int i=0;i<=tot;i+=2)eg[i].f+=eg[i^1].f,eg[i^1].f=0;
mxf=0,dinic();

矩形覆盖

https://atcoder.jp/contests/abc274/tasks/abc274_g

题意:给出一张矩阵,某些点处有障碍.每个点可以放置一台摄像机,选取四个方向中任一方向,对障碍前所有方格进行监视.除了障碍,所有点均需被监视.求出最小所用摄像头数.

首先,可以很明显的看出,对于放置于某格某方向的摄像头,如果反向的格子为空,那么此摄像头放在反向一定不会使答案更劣.所以所有的摄像头都应该沿着障碍物放置(此处将矩阵的边缘视为障碍物).

对于一条边的覆盖,两个端点只要有一个有该方向的覆盖就足够.所以只会有方向向下或向右的摄像头(向左,向上同理).

现在题意被转化为,在一个联通块的上边缘和左边缘放置摄像头,使得达到全覆盖.似乎除了dp之外想不到其他的方法,但是状压dp的复杂度不对,插头dp更是没有必要.试着再次换一个角度,考虑每个点如果能达成覆盖需要满足的条件.当前仅当每个点能到达的最左点或最上点中至少其一放置摄像头,全图完成覆盖.现在题意是,有若干个二元组,每个二元组中至少一个数被选取,求最小选取数.

这张图其实是一张二分图,问题就变成求解二分图的最小覆盖.根据Dilworth定理,建图后跑最大流即可求出.

iFor(i,n,1)iFor(j,m,1){
    if(!mp[i][j])continue;
    dn[i][j]=rt[i][j]=p;
    if(mp[i+1][j])dn[i][j]=dn[i+1][j]; 
    if(mp[i][j+1])rt[i][j]=rt[i][j+1];
    con(S,p,1),con(p+n*m,T,1),con(dn[i][j],rt[i][j]+n*m,INF); 
}