网络流学习笔记

P.S.

本来没想这么早就学网络流，但是似乎学姐说dinic的板子她就不讲了？那就先补一下dinic算法，详细的原理/优化/细节以后再补充。

最小费用最大流的话目前只介绍基于EK算法的MCMF，原始对偶或者zkw以后再补。

什么是网络流

什么是最大流

这里咱们先来说网络流中最简单的一种，叫做最大流。
我们有一个有向图，这个图有一个源点，有一个汇点，每条边都有一个流量，最大流就是单位时间内汇点可以接收到的最大流量。

什么是最小费用最大流

在一个网络流中，最大流可能有很多个。

对于每条边我们都有一个单位流量的费用，我们要求的就是最大流中费用最小的那个。

网络流的实现

dinic的实现

dinic算法先要建反边(我也不知道为啥)；然后进行不断BFS，进行分层，也就是算出每个点对于源点的最短路径；每一次BFS后都要不断深搜找增广路直到找不到为止，也就是对于每一条从源点到汇点的路径，算出这条路径上的最大流量，之后这条路径上的每条边都要减去这个最大流量，它们的反边都要加上这个流量。最后每次dfs累计的流量就是最大流。
对于dinic算法有一个优化，就是当前弧优化——这个我也不知道原理，但是在下面的板子里面我会标出来。

dinic板子

#include<iostream>
#include<cstdio>
#include<cstring>
#define rint register int
#define inv inline void
#define ini inline int
#define inb inline bool
#define big 1e9
using namespace std;
int dis[100001],n,m,s,t,q[100001],ans,cnt=-1,head[2000001],tot,cur[2000001];
struct node
{
	int next,to,dis,cnt;
}ljb[2000001];
inv add(int x,int y,int z)
{
	ljb[++cnt].next=head[x];
	ljb[cnt].to=y;
	ljb[cnt].dis=z;
	ljb[cnt].cnt=cnt;
	head[x]=cnt;
}
inb bfs()
{
	int hed=0,tail=1;
	memset(dis,128,sizeof(dis));
	q[1]=s;dis[s]=0;
	while (hed<tail)
	{
		int x=q[++hed];
		for (rint i=head[x];i>=0;i=ljb[i].next)
		{
			int y=ljb[i].to;
			if (dis[y]<0 && ljb[i].dis>0)
			{
				dis[y]=dis[x]+1;
				q[++tail]=y;
			}
		}
	}	
	if (dis[t]>0) return 1;
	return 0;
}
ini dinic(int x,int low)
{
	if (x==t) return low;
	for (rint& i=cur[x];i>=0;i=ljb[i].next)
	//当前弧优化 第一处↑
	{
		int y=ljb[i].to;
		if (dis[y]==dis[x]+1 && ljb[i].dis>0)
		{
			int kk=dinic(y,min(ljb[i].dis,low));
			if (kk) 
			{
				ljb[i].dis-=kk;
				ljb[ljb[i].cnt^1].dis+=kk;
				return kk;
			}
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for (rint i=1;i<=n;i++) head[i]=-1;
	for (rint i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,0);
	}
	while (bfs())
	{
		for (rint i=1;i<=n;i++) cur[i]=head[i];
		//当前弧优化，第二处↑
		do
		{
			tot=dinic(s,big);
			ans+=tot;
		}
		while (tot);
	}
	printf("%d",ans);
}

MCMF的实现

在介绍MCMF之前，我们先说一下最大流的EK算法。

EK算法就是不断进行BFS，每次只找一条增广路，不断增广直到流空。

MCMF的实现可以认为是在BFS的过程中每次都找费用最小的边进行增广，我们可以用同样基于BFS的spfa算法实现，每次以费用为边权跑最短路，即为费用最小的一条增广路，记录这条路上的最大流，然后进行计算。这里需要注意，我们的反边的费用是正边费用的相反数。

MCMF板子

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define inb inline bool
#define ini inline int
#define big 1e9
#define maxn 100010
using namespace std;
int n,m,s,t,ans1,ans2,cnt;
int head[maxn],dis[maxn],pre[maxn],lst[maxn],flow[maxn];
bool vis[maxn];
queue<int> q; 
ini read()
{
	char c;int r=0,f=1;
	while (c<'0' || c>'9')
	{
		c=getchar();
		if (c=='-') f=-1;
	}
	while (c>='0' && c<='9')
	{
		r=r*10+c-'0';
		c=getchar();
	}
	return r*f;
}
struct node
{
	int next,to,flow,dis;
}ljb[maxn];
inv add_edge(int x,int y,int z,int f)
{
	ljb[++cnt].next=head[x];
	ljb[cnt].to=y;
	ljb[cnt].flow=z;
	ljb[cnt].dis=f;
	head[x]=cnt;
}
inv add(int x,int y,int z,int f)
{
	add_edge(x,y,z,f);
	add_edge(y,x,0,-f);
}
inv some_pre()
{
	for (rint i=1;i<=n;i++) flow[i]=big;
	for (rint i=1;i<=n;i++) dis[i]=big;
	for (rint i=1;i<=n;i++) vis[i]=0;
	q.push(s);dis[s]=0;vis[s]=1;pre[t]=-1;
} 
inb spfa()
{
	some_pre();
	while (!q.empty())
	{
		int x=q.front();q.pop();vis[x]=0;
		for (rint i=head[x];i!=-1;i=ljb[i].next)
		{
			int y=ljb[i].to;
			if (ljb[i].flow>0 && dis[y]>dis[x]+ljb[i].dis)
			{
				dis[y]=dis[x]+ljb[i].dis;
				pre[y]=x;lst[y]=i;
				flow[y]=min(flow[x],ljb[i].flow);
				if (!vis[y])
				{
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
	if (pre[t]!=-1) return 1;
	return 0;
}
int main()
{
	n=read();m=read();s=read();t=read();
	for (rint i=1;i<=n;i++) head[i]=-1;cnt=-1;
	for (rint i=1;i<=m;i++)
	{
		int x,y,z,f;
		x=read();y=read();z=read();f=read();
		add(x,y,z,f);
	}
	while (spfa())
	{
		int x=t;
		ans1+=flow[t];
		ans2+=flow[t]*dis[t];
		while (x!=s)
		{
			ljb[lst[x]].flow-=flow[t];
			ljb[lst[x]^1].flow+=flow[t];
			x=pre[x];
		}
	}
	printf("%d %d",ans1,ans2);
}

最大流例题

luogu2756 飞行员配对方案问题

网络流难就难在建图。dinic在大多数情况下只是一个工具，怎么建图才是关键。
这个题建图还好说，就是自己造一个源点一个汇点，源点连接外国人，汇点连接英国人就可以了。关键是怎么输出方案的问题。
对于这个题来说，去掉连接源点的边和连接汇点的边，其它两个边之间最多有一条边。也就是说这要跑到最后这条边的反边不是零，就说明这条边在最大流里面(因为它没有反悔)，直接看所有的边，哪一条的反边不为0就说明选了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define inb inline bool
#define ini inline int
#define big 1e9
using namespace std;
int n,m,cnt,head[10001],cur[10001],dis[10001],ans,tot,xx,yy;
struct node
{
	int from,to,dis,num,next;
}ljb[10001];
inv add(int x,int y,int z)
{
	ljb[++cnt].from=x;
	ljb[cnt].to=y;
	ljb[cnt].dis=z;
	ljb[cnt].num=cnt;
	ljb[cnt].next=head[x];
	head[x]=cnt;
}
queue<int> q;
inb bfs()
{
	q.push(0);
	memset(dis,128,sizeof(dis));
	dis[0]=0;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for (rint i=head[x];i!=-1;i=ljb[i].next)
		{
			int y=ljb[i].to;
			if (dis[y]<0 && ljb[i].dis>0)
			{
				dis[y]=dis[x]+1;
				q.push(y);
			}
		}
	}
	if (dis[n]>0) return 1;
	return 0;
}
ini dfs(int x,int low)
{
	if (x==n) return low;
	for (rint& i=cur[x];i!=-1;i=ljb[i].next)
	{
		int y=ljb[i].to;
		if (dis[y]==dis[x]+1 && ljb[i].dis>0)
		{
			int flow=dfs(y,min(low,ljb[i].dis));
			if (flow)
			{
				ljb[i].dis-=flow;
				ljb[ljb[i].num^1].dis+=flow;
				return flow;
			}
		}
	} 
	return 0;
} 
int main()
{
	scanf("%d%d",&m,&n);n++;cnt=-1;
	for (rint i=0;i<=n;i++) head[i]=-1;
	for (rint i=1;i<=m;i++) add(0,i,1),add(i,0,0);
	for (rint i=m+1;i<=n-1;i++) add(i,n,1),add(n,i,0);
	scanf("%d%d",&xx,&yy);
	while ((xx+yy)!=-2)
	{
		add(xx,yy,1);
		add(yy,xx,0);
		scanf("%d%d",&xx,&yy);
	}
	while (bfs())
	{
		for (rint i=0;i<=n;i++) cur[i]=head[i];
		do
		{
			tot=dfs(0,big);
			ans+=tot;
		}
		while (tot);
	}
	printf("%d\n",ans);
	if (!ans)
	{
		printf("No Solution!");
		return 0;
	}
	for (rint i=2*n-1;i<=cnt;i++)
		if (i%2 && ljb[i].dis>0)
			printf("%d %d\n",ljb[i].to,ljb[i].from);
}

luogu1345 奶牛的电信

乍一看还以为是一道水题，一开始想直接照搬板子，但好像旁边的ASIA大佬失败了？？
这不是最大流最小割吗？看题解。哦原来这个题还和最小割不一样，最小割是边，这个是点，是最小的割掉的点，我们要把这些电脑每一个都拆成两份，第一个连接它的直接源(注意不是超级源)，第二个连接它的直接汇，自己和自己之间边权为1，所以这条边只能走一次，这也是当然的，因为一个点只能被割掉一次。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define inb inline bool
#define ini inline int
#define big 1e9
using namespace std;
int n,m,cnt,head[10001],cur[10001],dis[10001],ans,tot,s,t;
struct node
{
	int to,dis,num,next;
}ljb[10001];
inv add(int x,int y,int z)
{
	ljb[++cnt].to=y;
	ljb[cnt].dis=z;
	ljb[cnt].num=cnt;
	ljb[cnt].next=head[x];
	head[x]=cnt;
}
queue<int> q;
inb bfs()
{
	q.push(s);
	memset(dis,128,sizeof(dis));
	dis[s]=0;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for (rint i=head[x];i!=-1;i=ljb[i].next)
		{
			int y=ljb[i].to;
			if (dis[y]<0 && ljb[i].dis>0)
			{
				dis[y]=dis[x]+1;
				q.push(y);
			}
		}
	}
	if (dis[t]>0) return 1;
	return 0;
}
ini dfs(int x,int low)
{
	if (x==t) return low;
	for (rint& i=cur[x];i!=-1;i=ljb[i].next)
	{
		int y=ljb[i].to;
		if (dis[y]==dis[x]+1 && ljb[i].dis>0)
		{
			int flow=dfs(y,min(low,ljb[i].dis));
			if (flow)
			{
				ljb[i].dis-=flow;
				ljb[ljb[i].num^1].dis+=flow;
				return flow;
			}
		}
	} 
	return 0;
} 
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	cnt=-1;
	for (rint i=1;i<=n*2;i++) head[i]=-1;
	for (rint i=1;i<=n;i++)
	{
		add(i,i+n,1);
		add(i+n,i,0);
	}
	for (rint i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x+n,y,big);
		add(y,x+n,0);
		add(y+n,x,big);
		add(x,y+n,0);
	}
	s+=n;n*=2;
	while (bfs())
	{
		for (rint i=1;i<=n;i++) cur[i]=head[i];
		do
		{
			tot=dfs(s,big);
			ans+=tot;
		}
		while (tot);
	}
	printf("%d",ans);
}

luogu2711小行星

这道题做的其实比较一波三折。一开始想出一个近似正解的思路，就是把面看做一个点，然后和上一个题一样操作。但是这样如果细想是不行的，正解应该是把x,y,z三个方向的面分开，超级源连接x点，这样割掉超级源和x之间的边就能删掉这个x，然后x连接y点，y要拆成两个点，y1和x连，y2和z连，只要删掉y1和y2之间的边就可把y点割掉，z点和超级汇连，只要删掉z点和超级汇之间的边就能把z点删掉。
后来因为一个小错误卡了老半天，连接y1和y2的时候把循环里的i写成yy了，极其zz，检查了好久……

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define inb inline bool
#define ini inline int
#define big 1e9
using namespace std;
int s=0,t=2001,n,m,sum,cnt,head[200001],cur[200001],dis[200001],ans,tot,xx,yy,zz,a[20001],b[20001],c[20001];
bool u1[2001][2001],u2[2001][2001],u3[2001][2001],u4[2001][2001];
struct node
{
	int to,dis,num,next;
}ljb[200001];
inv add_edge(int x,int y,int z)
{
	ljb[++cnt].to=y;
	ljb[cnt].dis=z;
	ljb[cnt].num=cnt;
	ljb[cnt].next=head[x];
	head[x]=cnt;
}
inv add(int x,int y)
{
	add_edge(x,y,1);
	add_edge(y,x,0);
}
queue<int> q;
inb bfs()
{
	q.push(s);
	memset(dis,128,sizeof(dis));
	dis[s]=0;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for (rint i=head[x];i!=-1;i=ljb[i].next)
		{
			int y=ljb[i].to;//cout<<y<<" ";
			if (dis[y]<0 && ljb[i].dis>0)
			{
				dis[y]=dis[x]+1;
				q.push(y);
			}
		}
	}
	if (dis[t]>0) return 1;
	return 0;
}
ini dfs(int x,int low)
{
	if (x==t) return low;
	for (rint& i=cur[x];i!=-1;i=ljb[i].next)
	{
		int y=ljb[i].to;
		if (dis[y]==dis[x]+1 && ljb[i].dis>0)
		{
			int flow=dfs(y,min(low,ljb[i].dis));
			if (flow)
			{
				ljb[i].dis-=flow;
				ljb[ljb[i].num^1].dis+=flow;
				return flow;
			}
		}
	} 
	return 0;
} 
int main()
{
	scanf("%d",&n);cnt=-1;
	for (rint i=s;i<=t;i++) head[i]=-1;
	for (rint i=1;i<=n;i++)
	{
		scanf("%d%d%d",&xx,&yy,&zz);
		if (!a[xx]) a[xx]=++sum;
		if (!b[yy]) 
		{
			b[yy]=++sum;
			b[yy+500]=++sum;
		};
		if (!c[zz]) c[zz]=++sum;
		if (!u1[s][xx]) u1[s][xx]=1,add(s,a[xx]);
		if (!u2[xx][yy]) u2[xx][yy]=1,add(a[xx],b[yy]);
		if (!u3[yy][zz]) u3[yy][zz]=1,add(b[yy+500],c[zz]);
		if (!u4[zz][t]) u4[zz][t]=1,add(c[zz],t);
	}
	for (rint i=0;i<=500;i++) 
		if (b[i]) add(b[i],b[i+500]); 
	while (bfs())
	{
		for (rint i=s;i<=t;i++) cur[i]=head[i];
		do
		{
			tot=dfs(s,big);
			ans+=tot;
		}
		while (tot);
	}
	printf("%d",ans);
}c

luogu1402 酒店之王

这题乍一看不是小行星吗。不用多说，只需要注意一个地方，就是这个题由于是客人又选房间又选菜，要把客人放中间，房间连接超级源，菜连接超级汇，注意建图细节，就OK了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define inb inline bool
#define ini inline int
#define big 1e9
using namespace std;
int n,m,p,q,cnt,head[250001],cur[250001],dis[10001],ans,tot,s=0,t=401;
bool a[101][101],b[101][101];
struct node
{
	int to,dis,num,next;
}ljb[250001];
inv add_edge(int x,int y,int z)
{
	ljb[++cnt].to=y;
	ljb[cnt].dis=z;
	ljb[cnt].num=cnt;
	ljb[cnt].next=head[x];
	head[x]=cnt;
}
inv add(int x,int y)
{
	add_edge(x,y,1);
	add_edge(y,x,0);
}
queue<int> que;
inb bfs()
{
	que.push(s);
	memset(dis,128,sizeof(dis));
	dis[s]=0;
	while(!que.empty())
	{
		int x=que.front();
		//cout<<x<<endl;
		que.pop();
		for (rint i=head[x];i!=-1;i=ljb[i].next)
		{
			int y=ljb[i].to;//cout<<y<<" ";
			if (dis[y]<0 && ljb[i].dis>0)
			{
				dis[y]=dis[x]+1;
				que.push(y);
			}
		}
		//cout<<endl;
	}
	if (dis[t]>0) return 1;
	return 0;
}
ini dfs(int x,int low)
{
	if (x==t) return low;
	for (rint& i=cur[x];i!=-1;i=ljb[i].next)
	{
		int y=ljb[i].to;
		if (dis[y]==dis[x]+1 && ljb[i].dis>0)
		{
			int flow=dfs(y,min(low,ljb[i].dis));
			if (flow)
			{
				ljb[i].dis-=flow;
				ljb[ljb[i].num^1].dis+=flow;
				return flow;
			}
		}
	} 
	return 0;
} 
int main()
{
	scanf("%d%d%d",&n,&p,&q);
	for (rint i=s;i<=t;i++) head[i]=-1;cnt=-1;
	for (rint i=1;i<=n;i++)
		for (rint j=1;j<=p;j++)
			cin>>a[i][j];
	for (rint i=1;i<=n;i++)
		for (rint j=1;j<=q;j++)
			cin>>b[i][j];
	for (rint i=1;i<=p;i++) add(s,i);
	for (rint i=1;i<=q;i++) add(i+300,t);
	for (rint i=1;i<=n;i++)
	{
		add(i+100,i+200);
		for (rint j=1;j<=p;j++)
			if (a[i][j])
				add(j,i+100);
		for (rint j=1;j<=q;j++)
			if (b[i][j])
				add(i+200,j+300);
	}	
	while (bfs())
	{
		for (rint i=s;i<=t;i++) cur[i]=head[i];
		do
		{
			tot=dfs(s,big);
			ans+=tot;
		}
		while (tot);
	}
	printf("%d",ans);
}

luogu2762 太空飞行计划问题

这题真的太费脑子了……一开始的想法太天真，就是先用源点连接仪器，然后仪器连实验，实验和实验自连，边权是实验的净收益，但是这样后来证明是不行的，因为题面的意思是多个实验可以共用一个仪器。所以说就算某个实验的收益为负数，但是它用到的仪器能为别的实验所用，那么就相当与你花了这个实验的赞助商给你的钱为别的实验买仪器。
实在想不出来，看题解。应该的建图方法是源点连接实验，边权是实验经费，实验和仪器之间连inf，然后仪器和汇点之间连接，边权是买仪器的钱，这样跑出来的最大流用总经费减去就行了。如果是亏本实验，流到最后的就是赞助商给的经费，所以最后用总经费减去最大流的时候就直接减去这个经费，就相当于没选这个实验。
对于之前pass掉我程序的那个想法，用这种建图也可以实现。
这个题最难的一点就在于如何输出方案。介入本人太蒟蒻，只能看题解。题解提供的方案是最后一遍增广的分层图中有层数的，也就是遍历到的点是选过的。这个大概的解释方法就是整张图看做最小割之后分成了两个集合，一个包括源点，一个包括汇点。
为什么要看做最小割呢？之前我们说过，如果某个实验的收益为负数，但是它用到的仪器能为别的实验所用，那么就相当与你花了这个实验的赞助商给你的钱为别的实验买仪器，具象化在这个图上，就是仪器那个点给这个实验一个流，把这个实验流出去的抵消掉了。当然，也会存在那种无论怎么买仪器都不划算的实验，这样的实验有一个特点，因为它不能供给仪器的需求，所以源点到它的残流一定是0，就是说不管是正向边还是反向边都是0，同样的那些可以供给的，源点到它的残留一定大于0，也就是正向边或者反向边大于0，说明做这个实验能赚钱。
那么，因为这种必须要删掉的实验，它的经费最终肯定要从总经费里面减掉，我们就不算它，而剩下的那些实验，它们所需要的仪器一起流到汇点，就是最大流。所以说，最小割也是割掉这些仪器与汇点之间的边。
由此我们可以证出，在最小割中，与源点同一集合的实验和仪器，必选。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define inb inline bool
#define ini inline int
#define big 1e9
using namespace std;
int n,m,all,cnt,head[10001],cur[10001],dis[10001],ans,tot,s=0,t=151;
bool flag;
struct node
{
    int from,to,dis,num,next;
}ljb[10001];
ini read()
{
    char c;int r=0;
    while (c<'0' || c>'9') c=getchar();
    while (c>='0' && c<='9')
    {
        r=r*10+c-'0';
        c=getchar();
    }
    if (c=='\r') flag=1;
    return r;
}
inv add(int x,int y,int z)
{
    ljb[++cnt].from=x;
    ljb[cnt].to=y;
    ljb[cnt].dis=z;
    ljb[cnt].num=cnt;
    ljb[cnt].next=head[x];
    head[x]=cnt;
}
queue<int> q;
inb bfs()
{
    q.push(s);
    memset(dis,128,sizeof(dis));
    dis[s]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for (rint i=head[x];i!=-1;i=ljb[i].next)
        {
            int y=ljb[i].to;
            if (dis[y]<0 && ljb[i].dis>0)
            {
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    if (dis[t]>0) return 1;
    return 0;
}
ini dfs(int x,int low)
{
    if (x==t) return low;
    for (rint& i=cur[x];i!=-1;i=ljb[i].next)
    {
        int y=ljb[i].to;
        if (dis[y]==dis[x]+1 && ljb[i].dis>0)
        {
            int flow=dfs(y,min(low,ljb[i].dis));
            if (flow)
            {
                ljb[i].dis-=flow;
                ljb[ljb[i].num^1].dis+=flow;
                return flow;
            }
        }
    } 
    return 0;
} 
int main()
{
    m=read();n=read();
    for (rint i=s;i<=t;i++) head[i]=-1;cnt=-1;
    for (rint i=1;i<=m;i++)
    {
        int x;x=read();all+=x;
        add(s,i,x);add(i,s,0);
        flag=0;
        while (!flag)
        {
            x=read();
            add(i,x+50,big);
            add(x+50,i,0);
        }
    }
    for (rint i=1;i<=n;i++)
    {
        int x;x=read();
        add(i+50,t,x);
        add(t,i+50,0);
    }
    while (bfs())
    {
        for (rint i=s;i<=t;i++) cur[i]=head[i];
        do
        {
            tot=dfs(s,big);
            ans+=tot;
        }
        while (tot);
    }
    for (rint i=1;i<=m;i++) if (dis[i]>0) cout<<i<<" ";
    printf("\n");
    for (rint i=1;i<=n;i++) if (dis[i+50]>0) cout<<i<<" ";
    printf("\n");
    printf("%d",all-ans);
 }

luogu2763 试题库问题

前几道都是看上去简单做起来难，这道题一上来看了我个一脸懵逼，咋回事啊？
仔细看其实特别简单，源点连接题的类别，流量是规定的个数，每个类别连接题目，流量为1，题目连接汇点，流量为1，就OK了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define inb inline bool
#define ini inline int
#define big 1e9
using namespace std;
int n,m,k,cnt,l[250000],f[1001][1001],head[250000],cur[250000],dis[250000],ans,tot,s=0,t=3333;
struct node
{
    int from,to,dis,num,next;
}ljb[250000];
ini read()
{
    char c;int r=0;
    while (c<'0' || c>'9') c=getchar();
    while (c>='0' && c<='9')
    {
        r=r*10+c-'0';
        c=getchar();
    }
    return r;
}
inv add_edge(int x,int y,int z)
{
    ljb[++cnt].from=x;
    ljb[cnt].to=y;
    ljb[cnt].dis=z;
    ljb[cnt].num=cnt;
    ljb[cnt].next=head[x];
    head[x]=cnt;
}
inv add(int x,int y,int z)
{
	add_edge(x,y,z);
	add_edge(y,x,0);
}
queue<int> q;
inb bfs()
{
    q.push(s);
    memset(dis,128,sizeof(dis));
    dis[s]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for (rint i=head[x];i!=-1;i=ljb[i].next)
        {
            int y=ljb[i].to;
            if (dis[y]<0 && ljb[i].dis>0)
            {
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    if (dis[t]>0) return 1;
    return 0;
}
ini dfs(int x,int low)
{
    if (x==t) return low;
    for (rint& i=cur[x];i!=-1;i=ljb[i].next)
    {
        int y=ljb[i].to;
        if (dis[y]==dis[x]+1 && ljb[i].dis>0)
        {
            int flow=dfs(y,min(low,ljb[i].dis));
            if (flow)
            {
                ljb[i].dis-=flow;
                ljb[ljb[i].num^1].dis+=flow;
                return flow;
            }
        }
    } 
    return 0;
} 
int main()
{
	k=read();n=read();
	for (rint i=s;i<=t;i++) head[i]=-1;cnt=-1;
	for (rint i=1;i<=k;i++) 
	{
		l[i]=read();m+=l[i];
		add(s,i,l[i]);
	}
	for (rint i=1;i<=n;i++)
	{
   		add(i+1000,t,1);
   		int p;p=read();
   		for (rint j=1;j<=p;j++)
   		{
   			int x;x=read();
   			add(x,i+1000,1);
		}
	} 
	while (bfs())
	{
		for (rint i=s;i<=t;i++) cur[i]=head[i];
		do
		{
			tot=dfs(s,big);
			ans+=tot;
		}
		while (tot);
	}
	if (ans<m) 
	{
		printf("No Solution!");
		return 0;
	}
	for (rint i=0;i<=cnt;i+=2)
		if (ljb[i].from!=s && ljb[i].to!=t)
		{
			if (ljb[i].dis==0) 
				f[ljb[i].from][++f[ljb[i].from][0]]=ljb[i].to-1000;
		}
	for (rint i=1;i<=k;i++)
	{
		cout<<i<<": ";
		for (rint j=1;j<=l[i];j++)
			cout<<f[i][j]<<" ";
		cout<<endl;
	}
}

luogu3153 跳舞

无知限制了我的想象力……完全没有思路，果然对于拆点这个东西还是懵逼的……
这道题不愧为省选+难度，%%%yyb神佬。
先说建图的方法吧：源点连接男生，汇点连接女生。每个男生和女生都被拆成两个点，一个与自己喜欢的相连，一个与自己不喜欢的相连，边权为1。自己与自己之间边权为k，这样就能够完美的限制男生只选k个不喜欢的女生了。
我们可以把这道题看做“能不能跳x首舞曲”(yyb神佬语)，所以可以二分x，如果最大流跑出来的结果是x*n，也就是n个女生都跳了x首舞曲，那么就可以，否之不行。这道题给我的启发还是很大的，在网络流中我们常常有一些限制，比如说这个题目中的k，我们可以把它具象为边权的形式，从这上面入手来答题。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define inb inline bool
#define ini inline int
#define big 1e9
using namespace std;
int n,m,k,cnt,head[500000],cur[500000],dis[500000],ans,tot,s=0,t=201,answer;
char c[101][101]; 
struct node
{
    int next,to,dis,num;
}ljb[500000];
ini read()
{
    char c;int r=0;
    while (c<'0' || c>'9') c=getchar();
    while (c>='0' && c<='9')
    {
        r=r*10+c-'0';
        c=getchar();
    }
    return r;
}
inv add_edge(int x,int y,int z)
{
    ljb[++cnt].next=head[x];
    ljb[cnt].to=y;
    ljb[cnt].dis=z;
    ljb[cnt].num=cnt;
    head[x]=cnt;
}
inv add(int x,int y,int z)
{
	add_edge(x,y,z);
	add_edge(y,x,0);
}
queue<int> q;
inb bfs()
{
    q.push(s);
    memset(dis,128,sizeof(dis));
    dis[s]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for (rint i=head[x];i!=-1;i=ljb[i].next)
        {
            int y=ljb[i].to;
            if (dis[y]<0 && ljb[i].dis>0)
            {
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    if (dis[t]>0) return 1;
    return 0;
}
ini dfs(int x,int low)
{
    if (x==t) return low;
    for (rint& i=cur[x];i!=-1;i=ljb[i].next)
    {
        int y=ljb[i].to;
        if (dis[y]==dis[x]+1 && ljb[i].dis>0)
        {
            int flow=dfs(y,min(low,ljb[i].dis));
            if (flow)
            {
                ljb[i].dis-=flow;
                ljb[ljb[i].num^1].dis+=flow;
                return flow;
            }
        }
    } 
    return 0;
} 
inv pre(int x)
{
	for (rint i=s;i<=t;i++) head[i]=-1;cnt=-1;ans=0;
	memset(ljb,0,sizeof(ljb));
	for (rint i=1;i<=n;i++)
		for (rint j=1;j<=n;j++)
			if (c[i][j]=='Y') add(i,j+150,1);
			else add(i+50,j+100,1);
	for (rint i=1;i<=n;i++) 
	{
		add(0,i,x);
		add(i,i+50,k);
		add(i+100,i+150,k);
		add(i+150,t,x);
	}
}
inb dinic(int x)
{
	pre(x);
	while (bfs())
	{
		for (rint i=s;i<=t;i++) cur[i]=head[i];
		do
		{
			tot=dfs(s,big);
			ans+=tot;
		}
		while (tot);
	}
	if (ans==x*n) return 1;
	return 0;
}
int main()
{
	n=read();k=read();
	for (rint i=1;i<=n;i++)
		for (rint j=1;j<=n;j++)
			cin>>c[i][j];
	int l=0,r=n*n;
	while (l<=r)
	{
		int mid=(l+r)/2;
		if (dinic(mid))
		{
			l=mid+1;
			answer=mid;
		}
		else r=mid-1;
	}
	printf("%d",answer);
}

luogu2057 善意的投票

这个被asia神蔑视的题，被夫神狂A三遍的题，malao轻松一遍过的题，GAY哥不屑于做的题，我竟然又抄了题解……
由此可见我的菜了。下面说一下题解里yyb神佬的建图方案，把同意午睡的与源点连接，反对午睡的与汇点连接，好朋友之间连双向边——因为只要一个妥协，这条路就不通了，这样求一个最小割就行了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int
#define inv inline void
#define inb inline bool
#define ini inline int
#define big 1e9
using namespace std;
int n,m,k,cnt,head[100000],cur[100000],dis[100000],ans,tot,s=0,t=1001,a[1001],b[1001];
struct node
{
    int from,to,dis,num,next;
}ljb[250000];
ini read()
{
    char c;int r=0;
    while (c<'0' || c>'9') c=getchar();
    while (c>='0' && c<='9')
    {
        r=r*10+c-'0';
        c=getchar();
    }
    return r;
}
inv add_edge(int x,int y,int z)
{
    ljb[++cnt].from=x;
    ljb[cnt].to=y;
    ljb[cnt].dis=z;
    ljb[cnt].num=cnt;
    ljb[cnt].next=head[x];
    head[x]=cnt;
}
inv add(int x,int y,int z)
{
	add_edge(x,y,z);
	add_edge(y,x,0);
}
queue<int> q;
inb bfs()
{
    q.push(s);
    memset(dis,128,sizeof(dis));
    dis[s]=0;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for (rint i=head[x];i!=-1;i=ljb[i].next)
        {
            int y=ljb[i].to;
            if (dis[y]<0 && ljb[i].dis>0)
            {
                dis[y]=dis[x]+1;
                q.push(y);
            }
        }
    }
    if (dis[t]>0) return 1;
    return 0;
}
ini dfs(int x,int low)
{
    if (x==t) return low;
    for (rint& i=cur[x];i!=-1;i=ljb[i].next)
    {
        int y=ljb[i].to;
        if (dis[y]==dis[x]+1 && ljb[i].dis>0)
        {
            int flow=dfs(y,min(low,ljb[i].dis));
            if (flow)
            {
                ljb[i].dis-=flow;
                ljb[ljb[i].num^1].dis+=flow;
                return flow;
            }
        }
    } 
    return 0;
} 
int main()
{
	n=read();m=read();
	for (rint i=s;i<=t;i++) head[i]=-1;cnt=-1;
	for (rint i=1;i<=n;i++)
	{
		int x=read();
		if (x==1) add(s,i,1),a[i]=1;
		else add(i+300,t,1),b[i]=1;
	}
	for (rint i=1;i<=m;i++)
	{
		int x,y;
		x=read();y=read();
		if (a[x]==1 && b[y]==1) 
		{
			add_edge(x,y+300,1);
			add_edge(y+300,x,1);
		}
		if (b[x]==1 && a[y]==1)
		{
			add_edge(y,x+300,1);
			add_edge(x+300,y,1);
		}
	}
	while (bfs())
	{
		for (rint i=s;i<=t;i++) cur[i]=head[i];
		do
		{
			tot=dfs(s,big);
			ans+=tot;	
		} 
		while (tot);
	}
	printf("%d",ans);
}

luogu3324 星际战争

好吧，我已经连看三道题解了……
这道题不看题解的时候自己的想法是很接近题解的，比之前的毫无思路可以说是有进步了。这道题的建图很明显，就是源点连接激光武器，激光连接机器人，机器人连接汇点，很明显是相当于源点给激光提供能量，激光打机器人，所以机器人和汇点之间的边应该是血量。
这个没想出来坏就坏在没有想到二分，所以一上来想到各种奇怪的思路，什么a[i]/b[i]之类的。还有一点就是因为这个激光不能同时打两个机器人，所以我一上来把源点到激光的边为b[i]的可能性否决了，但实际是不对的。因为先打一个再打另一个和先打另一个再打这个是没有区别的。
正确的思路:二分时间，然后源点到激光是time*b[i]，激光到机器人是inf。由于精度限制不大可以用long long 做，最后除以1000就行了。 PS：linux输出double类型用lf而不是llf

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define rint register int 
#define inv inline void
#define ini inline int
#define inb inline bool
#define inl inline long long
#define ll long long
using namespace std;
int n,m,a[101],b[101],cnt,s=0,t=101,f[101][101],head[10001],dis[10001],cur[10001];
double answer;
ll tot,ans,all;
ll big=1000000000000000000ll;
ll maxx=10000000000ll;
struct node
{
	int next,to,num;
	ll dis;
}ljb[10001];
ini read()
{
	char c;int r=0;
	while (c<'0' || c>'9') c=getchar();
	while (c>='0' && c<='9')
	{
		r=r*10+c-'0';
		c=getchar();
	}
	return r;
}
inv add_edge(int x,int y,ll z)
{
	ljb[++cnt].next=head[x];
	ljb[cnt].to=y;
	ljb[cnt].dis=z;
	ljb[cnt].num=cnt;
	head[x]=cnt;
}
inv add(int x,int y,ll z)
{
	add_edge(x,y,z);
	add_edge(y,x,0);
}
queue <int> q;
inv pre(ll x)
{
	for (rint i=s;i<=t;i++) head[i]=-1;cnt=-1;ans=0;
	memset(ljb,0,sizeof(ljb));
	for (rint i=1;i<=m;i++) add(s,i,x*b[i]);
	for (rint i=1;i<=n;i++) add(i+50,t,a[i]*1000);
	for (rint i=1;i<=m;i++)
		for (rint j=1;j<=n;j++)
			if (f[i][j]) add(i,j+50,big);
}
inb bfs()
{
	memset(dis,128,sizeof(dis));
	dis[s]=0;q.push(s);
	while (!q.empty())
	{
		int x=q.front();q.pop();
		for (rint i=head[x];i!=-1;i=ljb[i].next)
		{
			int y=ljb[i].to;
			if (dis[y]<0 && ljb[i].dis>0)
			{
				dis[y]=dis[x]+1;
				q.push(y);
			}
		}
	}
	if (dis[t]>0) return 1;
	return 0;
}
inl dfs(int x,ll low)
{
	if (x==t) return low;
	for (rint& i=cur[x];i!=-1;i=ljb[i].next)
	{
		int y=ljb[i].to;
		if (dis[y]==dis[x]+1 && ljb[i].dis>0)
		{
			ll flow=dfs(y,min(ljb[i].dis,low));
			if (flow)
			{
				ljb[i].dis-=flow;
				ljb[ljb[i].num^1].dis+=flow;
				return flow;
			}
		}
	}
	return 0;
}
inb dinic(ll x)
{
	pre(x);
	while (bfs())
	{
		for (rint i=s;i<=t;i++) cur[i]=head[i];
		do
		{
			tot=dfs(s,big);
			ans+=tot;
		}
		while (tot);
	}
	if (ans==all*1000) return 1;
	return 0;
}
int main()
{
	n=read();m=read();
	for (rint i=1;i<=n;i++) a[i]=read(),all+=a[i];
	for (rint i=1;i<=m;i++) b[i]=read();
	for (rint i=1;i<=m;i++)
		for (rint j=1;j<=n;j++)
			f[i][j]=read();
	ll l=0,r=maxx;
	while (l<=r)
	{
		ll mid=(l+r)/2;
		if (dinic(mid))
		{
			r=mid-1;
			answer=mid;
		}
		else l=mid+1;
	}
	printf("%.4llf",answer/1000);
}

关于dinic

关于dinic的题就先到这里，更难的题我会以解题报告的形式写出来。
这里总结一些可以用dinic解决的问题的解题方法。

题型

二分求解。一般题目中带有求最小的最大值(星际战争)或最大的最小值(跳舞)，优先考虑二分。二分出题目中要求的值或未知的值不失为一种思路。
最小割。一般这种题包括比较直白的那种，比如最少删掉多少(小行星)，也有比较隐晦的，比如选边站(善意的投票)，像这样的题可以考虑用最小割来理解建图更方便一些。
拆点。这样的题比如说自身有多种选择的时候考虑拆点(跳舞)，或者是把最小割点转化为最小割边(酒店之王)。
代码实现
边权基本都是正整数，不要往怪诞的方面去想。
注意初始化head,cnt,dis，特别注意i!=-1以及dis[t]>0
注意什么该用long long，什么改用int
windows下long long 用i64d(尤其xp)，linux下用lld；windows和linux下double用lf，long double 用llf。

费用流例题

luogu2045 方格取数加强版

一提到这个题我就想揍一个叫zyc的人……当初我没学MCMF的时候这人告诉我这题是个最大流来着，害得我干想了两个小时……

这题其实不难，算是费用流里面比较简单的了。

对于每个点，拆点之后还是套路一个点入流一个点出流，方便最小割，流量为k。点和自己之间连两条边，一条流量1费用x，另一条流量k-1费用0就可以了，然后求一个最大费用最大流。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue> 
#define rint register int
#define inv inline void
#define inb inline bool
#define inc inline char
#define ini inline int
#define big 1e9
#define maxn 100000
using namespace std;
int flow[maxn],dis[maxn],lst[maxn],pre[maxn],head[maxn];
int n,k,ans,s=0,t=5001,cnt;
bool vis[maxn];
inc gc()
{
	static char BUFF[1000000],*S=BUFF,*T=BUFF;
	return S==T&&(T=(S=BUFF)+fread(BUFF,1,1000000,stdin),S==T)?EOF:*S++; 
}
ini read()
{
	char c;rint r=0,f=1;
	c=gc();
	while (c<'0' || c>'9'){
		if (c=='-') f=-1;
		c=gc();
	}
	while (c>='0' && c<='9'){
		r=r*10+(c^48);
		c=gc();
	}
	return r*f;
}
struct node
{
	int next,to,flow,dis;
}ljb[maxn];
inv add_edge(int x,int y,int f,int c)
{
	ljb[++cnt].next=head[x];
	ljb[cnt].to=y;
	ljb[cnt].flow=f;
	ljb[cnt].dis=c;
	head[x]=cnt;
}
inv add(int x,int y,int f,int c)
{
	add_edge(x,y,f,c);
	add_edge(y,x,0,-c);
}
queue<int> q;
inv some_pre()
{
	for (rint i=s;i<=t;i++) 
		dis[i]=-1,flow[i]=big,pre[i]=-1,lst[i]=0,vis[i]=0;
	q.push(s);vis[s]=1;dis[s]=0;
}
inb spfa()
{
	some_pre();
	while (!q.empty()){
		rint x=q.front();q.pop();vis[x]=0;
		for (rint i=head[x];i!=-1;i=ljb[i].next){
			int y=ljb[i].to;
			if (dis[y]<dis[x]+ljb[i].dis && ljb[i].flow>0){
				dis[y]=dis[x]+ljb[i].dis;
				pre[y]=x;lst[y]=i;
				flow[y]=min(flow[x],ljb[i].flow);
				if (!vis[y]){
					vis[y]=1;
					q.push(y);
				}
			}
		}
	}
	if (pre[t]!=-1) return 1;
	return 0;
}
int main()
{
	n=read();k=read();
	for (rint i=s;i<=t;i++) head[i]=-1;cnt=-1;
	for (rint i=1;i<=n;i++)
		for (rint j=1;j<=n;j++){
			rint x=read(),now=(i-1)*n+j;
			add(now,now+2500,1,x);
			add(now,now+2500,k,0);
			if (i!=1) add(now-n+2500,now,k,0);
			if (j!=1) add(now-1+2500,now,k,0);
		}
	add(s,1,k,0);
	add(n*n+2500,t,k,0);
	while (spfa()){
		rint x=t;
		ans+=flow[t]*dis[t];
		while (x!=s){
			ljb[lst[x]].flow-=flow[t];
			ljb[lst[x]^1].flow+=flow[t];
			x=pre[x];
		}
	}
	printf("%d",ans);
}

传说中的骚操作