前言

坑还是要开的，能填几天就不知道了

最近在学网络流，那么著名的 网络流24题 怎么能不刷呢？

记录一下刷题记录，难度应该是由易到难吧。

前置知识：最大流（Dinic）。

同步更新于这里。

飞行员配对方案问题

飞行员配对方案问题

简化题意：

给出集合 \(A\) 与集合 \(B\) 的可行配对关系（\(|A|=n,|B|=m\)），求出两集合的最大匹配数。

这道题告诉我们二分图匹配的题目可以转化为网络流的题目。

方法是建立超级源点 \(s\) 和超级汇点 \(t\)，将 \(s\) 与集合 \(A\) 所有节点连边，\(t\) 与集合 \(B\) 所有节点连边，边权均为 \(1\)。

求出最大匹配数=最大流。（自证不难）

值得注意的是，常用的匈牙利算法为 \(O(nm)\)，而 Dinic 求最大匹配为 \(O(m\sqrt n)\)。

当然本题的数据较小，所以两种方法均可，我用的是匈牙利（码量小很多啊）。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#define N 110
#define M 100100
using namespace std;

int n,m,head[N],match[N],cnt=0,ans=0;
bool vis[N];
struct Edge{
	int nxt,to;
}ed[M];

int read(){
	int x=0,f=1;char c=getchar();
	while(c<‘0‘ || c>‘9‘) f=(c==‘-‘)?-1:1,c=getchar();
	while(c>=‘0‘ && c<=‘9‘) x=x*10+c-48,c=getchar();
	return x*f;
}

void add(int u,int v){
	ed[++cnt].nxt=head[u];
	ed[cnt].to=v;
	head[u]=cnt;
	return;
}

bool dfs(int u){
	for(int i=head[u];i;i=ed[i].nxt){
		int v=ed[i].to;
		if(vis[v]) continue;
		vis[v]=true;
		if(!match[v] || dfs(match[v])){
			match[v]=u;return true;
		}
	}
	return false;
}

int main(){
	n=read(),m=read()-n;
	int u=read(),v=read();
	while(u!=-1 && v!=-1){
		add(u,v),add(v,u);
		u=read(),v=read();
	}
	for(int i=1;i<=n;i++){
		memset(vis,false,sizeof(vis));
		if(dfs(i)) ++ans;
	}
	printf("%d\n",ans);
	for(int i=n+1;i<=n+m;i++)
		if(match[i]) printf("%d %d\n",match[i],i);
	return 0;
}

圆桌问题

圆桌问题

题意挺简单的，自己康吧。

不难看出单位和桌子作为两边的点，进行匹配。

具体建图方法：

1. 源点 \(s\) 与每个单位连接，流量为此单位的代表数。
2. 汇点 \(t\) 与每张桌子连接，流量为这个桌子能容纳的人数。
3. 每个单位与桌子之间连接，流量为 \(1\)。（每个单位最多有一个人在同一桌）

安排完之后跑最大流，如果 最大流=代表总人数 就表示可以安排。

然后根据残量网络中边权为 \(0\) 的边输出即可。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#define N 1010
#define M 100010
#define INF 0x3f3f3f3f 
using namespace std;

int n,m,s,t,sum=0,head[N],d[N],cnt=1;
struct Edge{
	int nxt,to,val;
}ed[M<<1];
queue<int>q;

int read(){
	int x=0,f=1;char c=getchar();
	while(c<‘0‘ || c>‘9‘) f=(c==‘-‘)?-1:1,c=getchar();
	while(c>=‘0‘ && c<=‘9‘) x=x*10+c-48,c=getchar();
	return x*f;
}

void add(int u,int v,int w){
	ed[++cnt].nxt=head[u];ed[cnt].to=v;ed[cnt].val=w;head[u]=cnt;
	ed[++cnt].nxt=head[v];ed[cnt].to=u;ed[cnt].val=0;head[v]=cnt;
}

bool bfs(){
	memset(d,0,sizeof(d));
	while(!q.empty()) q.pop();
	d[s]=1;q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u];i;i=ed[i].nxt){
			int v=ed[i].to,w=ed[i].val;
			if(w && !d[v]){
				d[v]=d[u]+1;
				if(v==t) return true;
				q.push(v);
			}
		}
	}
	return false;
}

int dinic(int u,int flow){
	if(u==t) return flow;
	int rest=flow;
	for(int i=head[u];i && rest;i=ed[i].nxt){
		int v=ed[i].to,w=ed[i].val;
		if(w && d[v]==d[u]+1){
			int k=dinic(v,min(rest,w));
			if(!k) d[v]=0;
			ed[i].val-=k;
			ed[i^1].val+=k;
			rest-=k;
		}
	}
	return flow-rest;
}

int main(){
	n=read(),m=read();
	s=0,t=n+m+1;
	for(int i=1;i<=n;i++){
		int a=read();sum+=a;//记录代表总数。
		add(s,i,a);
	}
	for(int i=1;i<=m;i++){
		int a=read();
		add(i+n,t,a);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			add(i,j+n,1);
	int ans=0,flow;
	while(bfs())
		if(flow=dinic(s,INF)) ans+=flow;
	if(ans<sum){puts("0");return 0;}
	puts("1");
	for(int u=1;u<=n;u++){
		for(int i=head[u];i;i=ed[i].nxt){
			int v=ed[i].to,w=ed[i].val;
			if(v!=s && !w) printf("%d ",v-n);//根据残量网络输出。
		}
		puts("");
	}
	return 0;
}

最小路径覆盖问题

最小路径覆盖问题

先用 \(n\) 条路径覆盖整张图，显然没有比这更多的覆盖方法了。

如果两个顶点有边相连，那么它们显然可以合并，同时路径覆盖数将减 \(1\)。

同时显然每个顶点只能与一个顶点合并，那么考虑拆点，进行最大匹配求最大合并数量。

那么显然答案就是 总点数-最大合并数。

拆点方法如下：

1. 将每个节点 \(i\) 拆成 \(x(i),y(i)\) 两个。（我的习惯是 \(x(i)=i,y(i)=i+n\)）
2. 连接源点 \(s\) 与每一个 \(x(i)\)。
3. 连接汇点 \(t\) 与每一个 \(y(i)\)。
4. 如果有 \(edge(i,j)\)，那么连接 \(x(i),y(j)\)。
5. 所有边的边权均为 \(1\)。

建议配合画图食用。

输出路径就很烦了，我的方法是并查集维护路径总数，再利用残量网络递归输出。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<queue>
#define N 510
#define M 100010
#define INF 0x3f3f3f3f
using namespace std;

int n,m,s,t,head[N],fa[N],d[N],cnt=1;
struct Edge{
	int nxt,frm,to,val;
}ed[M];
queue<int>q;

int read(){
	int x=0,f=1;char c=getchar();
	while(c<‘0‘ || c>‘9‘) f=(c==‘-‘)?-1:1,c=getchar();
	while(c>=‘0‘ && c<=‘9‘) x=x*10+c-48,c=getchar();
	return x*f;
}

void add(int u,int v,int w){
	ed[++cnt]=(Edge){head[u],u,v,w};head[u]=cnt;
	ed[++cnt]=(Edge){head[v],v,u,0};head[v]=cnt;
}

void build(){//建图。
	n=read(),m=read();
	s=0,t=n<<1|1;
	for(int i=1;i<=m;i++){
		int u=read(),v=read();
		add(u,v+n,1);
	}
	for(int i=1;i<=n;i++) add(s,i,1);
	for(int i=1;i<=n;i++) add(i+n,t,1);
	return;
}

bool bfs(){
	while(!q.empty()) q.pop();
	memset(d,0,sizeof(d));
	d[s]=1;q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u];i;i=ed[i].nxt){
			int v=ed[i].to,w=ed[i].val;
			if(w && !d[v]){
				d[v]=d[u]+1;
				if(v==t) return true;
				q.push(v);
			}
		}
	}
	return false;
}

int Dinic(int u,int flow){
	if(u==t) return flow;
	int rest=flow;
	for(int i=head[u];i && rest;i=ed[i].nxt){
		int v=ed[i].to,w=ed[i].val;
		if(w && d[v]==d[u]+1){
			int k=Dinic(v,min(rest,w));
			if(!k) d[v]=0;
			ed[i].val-=k;
			ed[i^1].val+=k;
			rest-=k;
		}
	}
	return flow-rest;
}

int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}

void Print(int u){
	printf("%d ",u);
	for(int i=head[u];i;i=ed[i].nxt)
		if(!ed[i].val && ed[i].to>n)
			Print(ed[i].to-n);//递归输出。
	return;
}

void work(){
	int flow,ans=0;
	while(bfs())
		if(flow=Dinic(s,INF)) ans+=flow;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=2;i<=cnt;i++){
		int u=ed[i].frm,v=ed[i].to,w=ed[i].val;
		if(u>s && u<=n && v>n && v<t && !w)//找到被匹配了的边，表示这两点被合并了。
			fa[find(v-n)]=find(u);
        //与一般并查集不同的是 v-n 和 u 的顺序不可调换。
        //因为 u 在路径上的位置必然在 v-n 之前，而路径的输出需要考虑递归的顺序。
	}
	for(int i=1;i<=n;i++)
		if(fa[i]==i) Print(i),puts("");
	printf("%d\n",n-ans);
	return;
}

int main(){
	build();
	work();
	return 0;
}

网络流 24 题

原文：https://www.cnblogs.com/lpf-666/p/13447062.html