网络流建模练习

刷题

不定时更新

P1402 酒店之王

先将每个人建一个点，再建一个总源点向所有房间连边流量为1，每间房向对应的客人连边也是1，客人向每个喜欢的菜连1边，菜全部向汇点连1边

这样做存在问题，没有约束一个人只能拿一个，考虑拆点约束，把一个客人拆成两个，一个负责接受房间，一个负责拿菜，两个点之间连1边

就好了

代码实现是ez的

#include<bits/stdc++.h>
using namespace std;
const int N=3005;
const int inf=1e9;
struct edge{
    int v,w,nxt;
}e[N*2];
int hd[N],cur[N],tot=1;
void add(int u,int v,int w){
    e[++tot]={v,w,hd[u]},hd[u]=tot;
    e[++tot]={u,0,hd[v]},hd[v]=tot;
}
int n,p,q;
int s,t;
int dis[N];
bool bfs(){
    for(int i=1;i<=t;i++) dis[i]=inf;
    dis[s]=0;
    queue<int> Q;
    Q.push(s);
    cur[s]=hd[s];
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        for(int i=hd[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(e[i].w>0 and dis[v]==inf){
                cur[v]=hd[v];
                dis[v]=dis[u]+1;
                Q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int dinic(int u,int fl){
    if(u==t) return fl;
    int res=0;
    for(int i=cur[u];i;i=e[i].nxt){
        int v=e[i].v;
        cur[u]=i;
        if(e[i].w>0 and dis[v]==dis[u]+1){
            int k=dinic(v,min(fl,e[i].w));
            if(!k) dis[v]=inf;
            fl-=k,res+=k;
            e[i].w-=k,e[i^1].w+=k;
        }
        if(!fl) break;
    }
    return res;
}
int main(){
    cin>>n>>p>>q;
    s=2*n+p+q+1,t=s+1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=p;j++){
            int tmp;cin>>tmp;
            if(tmp) add(2*n+j,i,1);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=q;j++){
            int tmp;cin>>tmp;
            if(tmp) add(i+n,2*n+p+j,1);
        }
    }
    for(int i=1;i<=n;i++) add(i,i+n,1);
    for(int i=1;i<=p;i++){
        add(s,2*n+i,1);
    }
    for(int i=1;i<=q;i++){
        add(2*n+p+i,t,1);
    }
    int ans=0;
    while(bfs()){
        ans+=dinic(s,inf);
    }
    cout<<ans;
}

励志把dinic写的和LCT一样熟练（？）

P2756 飞行员配对方案问题

一眼丁真，鉴定为二分图匹配

参考上一题，源点连1向左部点，正常输入的边由左连右，也是1，最后右向汇连1

输出方案考虑 遍历左部点，看哪条残量网络为0就配对

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5;
const int inf=1e9;
int n,m;
int s,t;
struct edge{
    int v,w,nxt;
}e[N*2];
int hd[N],cur[N],tot=1;
void add(int u,int v,int w){
    e[++tot]={v,w,hd[u]},hd[u]=tot;
    e[++tot]={u,0,hd[v]},hd[v]=tot;
}
int dis[N];
bool bfs(){
    for(int i=1;i<=t;i++) dis[i]=inf; 
    dis[s]=0;
    queue<int> Q;
    Q.push(s);
    cur[s]=hd[s];
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        for(int i=hd[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(dis[v]==inf and e[i].w>0){
                dis[v]=dis[u]+1;
                Q.push(v);
                cur[v]=hd[v];
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int dinic(int u,int fl){
    if(u==t) return fl;
    int res=0;
    for(int i=cur[u];i;i=e[i].nxt){
        cur[u]=i;
        int v=e[i].v;
        if(e[i].w and dis[v]==dis[u]+1){
            int k=dinic(v,min(fl,e[i].w));
            if(!k) dis[v]=inf;
            res+=k,fl-=k;
            e[i].w-=k,e[i^1].w+=k;
        }
        if(!fl) break;
    }
    return res; 
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    s=m+1,t=s+1;
    for(int i=1;i<=n;i++){
        add(s,i,1);
    }
    for(int i=n+1;i<=m;i++){
        add(i,t,1);
    }
    while(1){
        int u,v;
        cin>>u>>v;
        if(u==-1) break;
        add(u,v,1);
    }
    int ans=0;
    while(bfs()){
        ans+=dinic(s,inf);
    }
    cout<<ans<<"\n";
    for(int u=1;u<=n;u++){
        for(int i=hd[u];i;i=e[i].nxt){
            if(e[i].v!=s and e[i].w==0){
                cout<<u<<" "<<e[i].v<<"\n";
                break;
            }
        }
    }
}

P1345 [USACO5.4] 奶牛的电信

原图正常边连inf流量，一个点拆成两个一个处理进边一个处理出边连1流量，然后转化为了最小割模型，跑最大流即可

顺带一提的是拆点的映射方式，除了可以是 $i$ 和 $i+n$ 以外也可以类似线段树写 $i\times 2$ 和 $i\times 2 +1$

当然习惯还是写 $+n$ 版本了（

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
const int inf=1e9;
struct edge{
    int v,w,nxt;
}e[N*2];
int hd[N],cur[N],tot=1;
void add(int u,int v,int w){
    e[++tot]={v,w,hd[u]},hd[u]=tot;
    e[++tot]={u,0,hd[v]},hd[v]=tot;
}
int n,m,s,t;
int  dis[N];
bool bfs(){
    for(int i=1;i<=n*2;i++){
        dis[i]=inf;
    }
    dis[s]=1;
    queue<int> Q;
    Q.push(s);
    cur[s]=hd[s];
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        for(int i=hd[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(e[i].w>0 and dis[v]==inf){
                dis[v]=dis[u]+1;
                cur[v]=hd[v];
                Q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
int dinic(int u,int fl){
    if(u==t) return fl;
    int res=0;
    for(int i=cur[u];i;i=e[i].nxt){
        int v=e[i].v;
        cur[u]=i;
        if(e[i].w>0 and dis[v]==dis[u]+1){
            int k=dinic(v,min(fl,e[i].w));
            if(!k) dis[v]=inf;
            res+=k,fl-=k;
            e[i].w-=k,e[i^1].w+=k;
        }
        if(!fl) break; 
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s>>t;
    s+=n;
    for(int i=1;i<=n;i++){
        add(i,i+n,1);
    }
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(n+u,v,inf);
        add(v+n,u,inf);
    }
    int ans=0;
    while(bfs()){
        ans+=dinic(s,inf);
    }
    cout<<ans;
}

最小割边数量

在最小割的前提下求最小割边数量，只需要先跑一次然后把没有满流的边设为inf，满流设为1，再跑一遍即可

两者取一模型

将一个集合的元素（设集合为 $S$ ）划分入 $A,B$ 两个集合，对于元素 $e_i$，其分入两个集合分别可以获得 $A_{e_i}$ 或 $B_{e_i}$ 的价值，除此之外还可以有若干组合使得某些物品同时放入某个集合有额外的价值，求最大价值

我们先不考虑组合的存在，我们可以建模： $A\to e_i\to B$，答案就是边权总和减去最小割，显然的

这里涉及到一个建模技巧：在最小割建模中，如果若干条边要断一条后就会导致不连通，但是只有一条是符合题目意思真的想断的，那就把另外几个全部赋inf就好了。无穷大是不会纳入最小割的，一定不优

于是我们让 $A$ 向组合 $X$ 连价值边，然后组合 $X$ 向目标点连inf边

全放 $B$ 的同理