[泛做]网络流最大流泛做

P3254 圆桌问题

有来自 \(m\) 个不同单位的代表参加一次国际会议。第 \(i\) 个单位派出了 \(r_i\) 个代表。

会议的餐厅共有 \(n\) 张餐桌，第\(i\) 张餐桌可容纳 \(c_i\) 个代表就餐。

为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。请给出一个满足要求的代表就餐方案。

若存在方案则输出 \(1\)，否则输出 \(0\)，若存在请给出任意一种方案

网络流的二分图匹配问题，把 \(m\) 个单位看作二分图的左部点，把 \(n\) 个餐桌看作二分图的右部点，从源点向左部点

各连一条边，容量为 \(r _i\) ，汇点也类似的连向右部点，把一个人看作一条边所以每个左部点都向右部点连一条容量

为 \(1\) 的边，求最大流即可

至于方案，先判断最大流是否等于总人数，然后看每条边（二分图内的）的反向边是否为 \(0\) 即可

#include 
#include 
#include 
#include 
#include 

P2763 试题库问题

假设一个试题库中有 \(n\) 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库

中抽取 \(m\) 道题组成试卷。并要求试卷包含指定类型指定个数的试题。试设计一个满足要求的组卷算法。

理解题意是这道题的一大难处，简单来说就是选 \(n\) 个点，每个点有一个或者多个属性，最后选出 \(m\) 个点要求每种

属性的个数和要求一致

很明显，这又是一道网络流匹配的问题，左部点为事体，右边为属性，由于一道题只能选一次，所以从源点向每

道题连一个容量为 \(1\) 的边，也因此每个左部点也向右部点连容量为 \(1\) 的边，然后右部点连向汇点，容量为每种属

性的指定个数即可

不过这道题给了我一个教训：做网络流的题目要注意每个东西对应到图是什么编号，因为可能建图的时候可能和

实际不同

signed main(){
    k=read();n=read();
    s=0,t=k+n+1;
    for(int i=1+n;i<=k+n;++i){
	r[i]=read();
	m+=r[i];
	add(i,t,r[i]);
	add(t,i,0);
    }
    for(int i=1;i<=n;++i){
	add(s,i,1);
	add(i,s,0);
	int p=read();
	for(int j=1;j<=p;++j){
	    int bel=read();
	    add(i,bel+n,1);//这里调了好久
	    add(bel+n,i,0);
	}
    }
    int res=0;
    while(bfs()) res+=dinic(s,inf);
    if(res!=m) printf("No Solution!");
    else{
	for(int u=1+n;u<=n+k;++u){
	    printf("%lld: ",u-n);
	    for(int i=head[u];i;i=nxt[i]){
		if(ver[i^1]!=s&&ver[i^1]!=t&&ver[i]!=s&&ver[i]!=t)
		    if(val[i]) printf("%lld ",ver[i]);
	    }
	    printf("\n");
	}
    }
    return 0;
}

P1231 教辅的组成

已知一个完整的书册均应该包含且仅包含一本书、一本练习册和一份答案，然而现在全都乱做了一团许多书

上面的字迹都已经模糊了，然而 \(HansBug\) 还是可以大致判断这是一本书还是练习册或答案，并且能够大致

知道一本书和答案以及一本书和练习册的对应关系 \(HansBug\) 想知道在这样的情况下，最多可能同时组合成

多少个完整的书册。

还是一道网络流的匹配问题，不过需要用到一个小 \(trick\)

和之前的题一样，首先想象怎么建模，我们很快就能建出由“册，书，案”三部分构成构成的图，然后跑最大流，然

就开心地交了上去，发现自己 \(WA\) 了，为什么呢？

图是蒯的（

发现如果这样做的话，同一本书可能会被用到很多次，于是乎，我们就要用到拆点的思想，让中间的点

只能流出 \(1\) 的流量，可以得到下图

这样就可以直接跑最大流了

不过这类题目建图是真的麻烦，为了不再建图上出差错，我们可以现在草稿纸上记录每层点的个数，然后下一层

的点就是前面每层点的个数总和加上这个点在这一层的位置

signed main(){
    n1=read();n2=read();n3=read();
    m1=read();
    s=0,t=n2+2*n1+n3+1;
    for(int i=1;i<=n2;i++){
	add(s,i,1);
	add(i,s,0);
    }
    for(int i=1;i<=m1;++i){
	int x=read(),y=read();
	add(y,x+n2,1);
	add(x+n2,y,0);
    }
    for(int i=1+n2;i<=n2+n1;++i){
	add(i,i+n1,1);
	add(i+n1,i,0);
    }
    m2=read();
    for(int i=1;i<=m2;++i){
	int x=read(),y=read();
	x+=n1+n2;y+=2*n1+n2;
	add(x,y,1);
	add(y,x,0);
    }
    for(int i=1+n1+n2+n1;i<=n1+n2+n1+n3;++i){
	add(i,t,1);
	add(t,i,0);
    }
    int res=0;
    while(bfs()) res+=dinic(s,inf);
    printf("%lld",res);
    return 0;
}

P1345 [USACO5.4]奶牛的电信Telecowmunication

给定一张图和两个点 \(c1,c2\)，求要去掉最少个少个点才能使这两个点不连通？

割点裸题

这里只要知道一个 \(trick\) 就行了，拆点（怎么又是拆点

我们只要把每个点拆成两个点，分成 \(i,i+n\)，前面一个连进入的边，后面一个连出去的边，两个点之前连一个边

权为 \(1\) 的边，原图的边都为 \(inf\) 然后跑最大流就行了

P2598 [ZJOI2009]狼和羊的故事

很明显，这是最小割问题，按照题意，我们只需要让狼和羊的领土不连通即可，所以我们从源点向每一个羊连权

值无限大的边，狼则类似的连向汇点，然后每个点向四周连权值为 \(1\) 的点即可

#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
const int inf=1e18;
const int N=2e6+10;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int n,m,s,t,head[N],nxt[N],val[N],tot=1,d[N],now[N],ver[N];
int a[456][456];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
inline void add(int x,int y,int z){
    ver[++tot]=y,nxt[tot]=head[x],val[tot]=z,head[x]=tot;
    ver[++tot]=x,nxt[tot]=head[y],val[tot]=0,head[y]=tot;
}
inline int get(int i,int j){
    return (i-1)*m+j;
}
bool bfs(){
    for(int i=s;i<=t;i++) now[i]=head[i],d[i]=inf;
    queue q;
    q.push(s);d[s]=0;
    while(!q.empty()){
	int u=q.front();q.pop();
	for(int i=head[u];i;i=nxt[i]){
	    int v=ver[i];
	    if(val[i]&&d[v]==inf){
		d[v]=d[u]+1;
		q.push(v);
		if(v==t) return 1;
	    }
	}
    }
    return 0;
}
int dinic(int u,int sum){
    if(u==t||!sum) return sum;
    int ret=0;
    for(int i=now[u];i;i=nxt[i]){
	int v=ver[i];
	now[u]=i;
	if(val[i]&&d[v]==d[u]+1){
	    int k=dinic(v,min(sum-ret,val[i]));
	    if(!k) d[v]=inf;
	    val[i]-=k;val[i^1]+=k;
	    ret+=k;
	    if(ret==sum) return sum;
	}
    }
    return ret;
}
signed main(){
    n=read();m=read();
    s=0,t=n*m+1;
    for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j)
	    a[i][j]=read();
    for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j)
	    if(a[i][j]==1) add(s,get(i,j),inf);
	    else if(a[i][j]==2) add(get(i,j),t,inf);
    for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j)
	    for(int k=0;k<4;++k){
		int x=i+dx[k];
		int y=j+dy[k];
		if(x>=1&&x<=n&&y<=m&&y>=1) add(get(i,j),get(x,y),1);
	    }
    int res=0;
    while(bfs()) res+=dinic(s,inf);
    cout<