网络流24题题解（持续更新中）
太空飞行计划
最大权闭合子图模板。
贴个链接：https://www.cnblogs.com/dilthey/p/7565206.html
（以后再补）
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 5e3+5;
const ll INF = 1e18;
int m,n;
int dep[MAXN],now[MAXN],Ans[MAXN];
struct E
{
int to,pre;ll w;
}e[MAXN<<1];
int head[MAXN],tot_E=1;
void add(int u,int v,ll w)
{
e[++tot_E]={v,head[u],w};
head[u]=tot_E;
}
bool bfs()
{
memset(dep,0,sizeof dep);
queue <int> q;
q.push(0);dep[0]=1;
while(!q.empty())
{
int p=q.front();
q.pop();
now[p]=head[p];
for(int i=head[p];i;i=e[i].pre)
{
int to=e[i].to;ll w=e[i].w;
if(w&&!dep[to])
{
dep[to]=dep[p]+1;
q.push(to);
}
}
}
return dep[m+n+1];
}
ll dfs(int p,ll in)
{
if(p==m+n+1) return in;
ll out=0;
for(int i=now[p];i&∈i=e[i].pre)
{
now[p]=i;
int to=e[i].to;ll w=e[i].w;
if(w&&dep[to]==dep[p]+1)
{
ll res=dfs(to,min(in,w));
e[i].w-=res;
e[i^1].w+=res;
out+=res;
in-=res;
}
}
if(out==0) dep[p]=0;
return out;
}
int main()
{
scanf("%d %d",&m,&n);
ll ans=0;
for(int i=1;i<=m;++i)
{
int u;char str;
scanf("%d",&u);ans+=u;
add(0,i,u);add(i,0,0);
while(scanf("%d%c",&u,&str)!=EOF)
{
add(i,u+m,INF);
add(u+m,i,0);
if(str=='\n'||str=='\r') break;
}
}
for(int i=1;i<=n;++i)
{
int c;scanf("%d",&c);
add(i+m,m+n+1,c);
add(m+n+1,i+m,0);
}
while(bfs()) ans-=dfs(0,INF);
for(int i=1;i<=m;++i)
if(dep[i]) Ans[++Ans[0]]=i;
for(int i=1;i<Ans[0];++i) printf("%d ",Ans[i]);
printf("%d\n",Ans[Ans[0]]);
Ans[0]=0;
for(int i=m+1;i<=n+m;++i)
if(dep[i]) Ans[++Ans[0]]=i-m;
for(int i=1;i<Ans[0];++i) printf("%d ",Ans[i]);
printf("%d\n",Ans[Ans[0]]);
printf("%lld\n",ans);
return 0;
}
最小路径覆盖
注意到一条路径除了头尾，位于路径中间的点的入度与出度恰好为 \(1\)。因此，我们可以将一个点拆为两个点，一个点表示出度，一个点表示入度，分别位于二分图的左部和右部。
题目给的边 \(u,v\) 相当于 \(u\) 的出度点连向 \(v\) 的入度点，由于每个点的出入度恰好为 \(1\)。在二分图的体现中就是左部中的点与右部中点的匹配。每个左部点只连向一个右部点，即路径中一个点连向一个点的后继，每个右部点只被一个左部点连，相当于路径中的一个点与这个点的前驱相连。而路径的头，尾比较特殊，可能只有后继，可能只有前驱，也可能前驱后继都没有（路径中只有一个点的情况）。这在二分图中是由出度点/入度点没有对应与之匹配的点体现出来的。
所以一个图的路径覆盖集的大小就是一张二分图的总点数 \(-\) 匹配点数。
那么我们要路径覆盖集大小最小，就得让匹配点数最大。
所以用网络流/匈牙利算法求出最大匹配即可。
输出方案可以枚举左部点，如果左部点未输出过，就迭代的遍历它的匹配点，它匹配点对应左部点的匹配点...
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 6e3+5;
const int INF = 0x3f3f3f3f;
struct E
{
int to,pre,w;
}e[MAXN<<1];
int head[MAXN],tot_E=1;
void add(int u,int v,int w)
{
e[++tot_E]=E{v,head[u],w};
head[u]=tot_E;
}
int n,m;
int dep[MAXN],now[MAXN],mat[MAXN];
bool vis[MAXN];
bool bfs()
{
queue <int> q;
memset(dep,0,sizeof dep);
q.push(0);dep[0]=1;
while(!q.empty())
{
int p=q.front();
q.pop();
now[p]=head[p];
for(int i=head[p];i;i=e[i].pre)
{
int to=e[i].to,w=e[i].w;
if(w&&!dep[to])
{
dep[to]=dep[p]+1;
q.push(to);
}
}
}
return dep[2*n+1];
}
int dfs(int p,int in)
{
if(p==2*n+1) return in;
int out=0;
for(int i=now[p];i&∈i=e[i].pre)
{
now[p]=i;
int to=e[i].to,w=e[i].w;
if(w&&dep[p]+1==dep[to])
{
int res=dfs(to,min(w,in));
e[i].w-=res;
e[i^1].w+=res;
out+=res;
in-=res;
}
}
if(out==0) dep[p]=0;
return out;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=m;++i)
{
int u,v;
scanf("%d %d",&u,&v);
add(u,v+n,1);add(v+n,u,0);
}
for(int i=1;i<=n;++i)
{
add(0,i,1);add(i,0,0);
add(i+n,2*n+1,1);add(2*n+1,n+i,0);
}
int ans=n;
while(bfs()) ans-=dfs(0,INF);
for(int i=1;i<=n;++i)
{
for(int j=head[i];j;j=e[j].pre)
{
int to=e[j].to,w=e[j].w;
if(w==0&&to>=n+1&&to<=2*n)
{
mat[i]=to;
break;
}
}
}
for(int i=1;i<=n;++i)
{
if(vis[i]) continue;
int x=i+n;
while(x)
{
x-=n;
vis[x]=1;
printf("%d ",x);
x=mat[x];
}
printf("\n");
}
printf("%d\n",ans);
return 0;
}
圆桌聚餐
每张桌子的容量是有限制的，每个代表团到每张桌子的人数也是有限制的。
那么我们可以想到网络流的一个性质：对于一个节点，它输出的流量与输入的流量是相等的。
以此，我们进行构图。
首先构建一个超级源点，将每一个代表团抽象成点，超级源点向每一个代表团连一条单向边，边权为代表团的人数。
再将每张桌子抽象成点，每个代表团向所有桌子都连一条权值为 \(1\) 的单向边。
再建立超级汇点。将每个桌子与超级汇点连一条单向边，边权为桌子的容量。
代表团向桌子输出流，相当于就是派人到那张桌子，而边权为 \(1\) 则保证了每个代表团只会向一张桌子派一个人。
而超级源点与超级汇点分别于代表团桌子连边，就是利用了上面那个性质，让他们输出与输入的流量相同。这保证每个代表团只会输出那么多人，也保证每个桌子只会接受那么多输入。
然后我们跑一遍最大流，如果最大流与代表数总和相等则说明存在方案。否则不存在。
输出方案详见代码。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int MAXE = 2e5+5;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e4+5;
struct E
{
int to,pre,w;
}e[MAXE<<1];
int head[MAXN],tot_E=1;
void add(int u,int v,int w)
{
e[++tot_E]=E{v,head[u],w};
head[u]=tot_E;
}
int now[MAXN],dep[MAXN],n,m;
bool bfs()
{
memset(dep,0,sizeof dep);
queue <int> q;q.push(0);dep[0]=1;
while(!q.empty())
{
int p=q.front();
q.pop();
now[p]=head[p];
for(int i=head[p];i;i=e[i].pre)
{
int to=e[i].to,w=e[i].w;
if(w&&!dep[to])
{
dep[to]=dep[p]+1;
q.push(to);
}
}
}
return dep[n+m+1];
}
int dfs(int p,int in)
{
if(p==n+m+1) return in;
int out=0;
for(int i=now[p];i&∈i=e[i].pre)
{
now[p]=i;
int to=e[i].to,w=e[i].w;
if(w&&dep[to]==dep[p]+1)
{
int res=dfs(to,min(in,w));
e[i].w-=res;
e[i^1].w+=res;
out+=res;
in-=res;
}
}
if(!out) dep[p]=0;
return out;
}
int main()
{
scanf("%d %d",&m,&n);
for(int i=1;i<=m;++i)
{
for(int j=1;j<=n;++j)
{
add(i,j+m,1);
add(j+m,i,0);
}
}
int ans=0;
for(int i=1;i<=m;++i)
{
int x;scanf("%d",&x);ans+=x;
add(0,i,x);add(i,0,0);
}
for(int i=1;i<=n;++i)
{
int x;scanf("%d",&x);
add(i+m,n+m+1,x);add(n+m+1,i+m,0);
}
while(bfs()) ans-=dfs(0,INF);
if(ans==0)
{
printf("1\n");
for(int i=1;i<=m;++i)
{
for(int j=head[i];j;j=e[j].pre)
{
int to=e[j].to,w=e[j].w;
if(!w&&to>=m+1&&to<=m+n)
printf("%d ",to-m);
}
printf("\n");
}
}
else printf("0\n");
return 0;
}