首页 OI 模板

# 最大流和二分图匹配的模板

# 一、二分图匹配

二分图是一种特殊的图，图中每一条边所关联的两个节点都属于两个不同的点集，匹配的定义是在二分图的一个子图中任意一条边都不依附于同一个节点，称为是一个匹配，最大匹配是所有匹配中边数最多的匹配。

例题：二分图匹配

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=1001;

int n,m,E,rgh[N];
bool use[N],link[N][N];

bool find(int x)
{
	for(int i=1;i<=m;i++)
	{
		if(link[x][i] && !use[i])
		{
			use[i]=true;
			if(!rgh[i] || find(rgh[i]))
			{
				rgh[i]=x;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	scanf("%d %d %d",&n,&m,&E);
	for(int i=1;i<=E;i++)
	{
		int zuo,you;
		scanf("%d %d",&zuo,&you);
		if(zuo>n || you>m)
			continue;
		link[zuo][you]=true;
	}
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		memset(use,0,sizeof(use));
		if(find(i))
			sum++;
	}
	printf("%d\n",sum);
	return 0;
}

# 二、最大流

给定一个图，图中每一条边都有一个权值，把每一条边当做是水管，权值是就是最大流量，最大流问题，就是满足这些性质的情况下，源点到汇点的最大流量

例题：网络最大流

Code:

#include <bits/stdc++.h>
using namespace std;
const int N=100001;
struct node
{
	int to,len,id;
	node(int tt,int ll,int ii)
	{
		to=tt,len=ll,id=ii;
	}
	node()
	{
	}
};
vector <node > g[N];
vector <node > v[N];
int n,m,st,ed,pre[200001][2];
bool vis[N],flag[N];
queue <int > q;
bool bfs()
{
	q.push(st),vis[st]=true;
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		int size=g[t].size();
		for(int i=0;i<size;i++)
		{
			int to=g[t][i].to;
			int len=g[t][i].len;
			if(!vis[to] && len>0)
			{
				vis[to]=true;
				pre[to][0]=t,pre[to][1]=len;
				if(to==ed)
					return true;
				q.push(to);
			}
		}
	}
	return false;
}
void dfs(int cur,int &val)
{
	int size=v[cur].size();
	for(int i=0;i<size;i++)
	{
		if(v[cur][i].to==pre[cur][0])
		{
			flag[v[cur][i].id]=true;
			val=min(pre[cur][1],val);
			dfs(v[cur][i].to,val);
		}
	}
	return;
}
int ek()
{
	int ans=0;
	while(bfs())
	{
		int minn=0x7f7f7f7f;
		dfs(ed,minn);
		for(int i=1;i<=n;i++)
		{
			int s1=g[i].size();
			int s2=v[i].size();
			for(int j=0;j<s1;j++)
				if(flag[g[i][j].id])
					g[i][j].len-=minn;
			for(int j=0;j<s2;j++)
				if(flag[v[i][j].id])
					v[i][j].len+=minn;
		}
		ans+=minn;
		memset(vis,0,sizeof(vis));
		memset(flag,0,sizeof(flag));
		memset(pre,0,sizeof(pre));
		while(!q.empty()) q.pop();
	}
	return ans;
}
int main()
{
	scanf("%d %d %d %d",&n,&m,&st,&ed);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		g[a].push_back(node(b,c,i));
		v[b].push_back(node(a,0,i));
	}
	printf("%d\n",ek());
	return 0;
}

另一种写法：

#include <bits/stdc++.h>
using namespace std;
const int N=100001;
const int INF=0x7f7f7f7f;
struct node
{
	int to;
	int cap;
	int flink;
	node(int tt,int cc,int ff)
	{
		to=tt,cap=cc,flink=ff;
	}
	node()
	{
	}
};
vector <node > g[N];
bool vis[N];
int n,m,st,ed;
int dfs(int now,int aim,int val)
{
	if(now==aim)
		return val;
	vis[now]=true;
	int size=g[now].size();
	for(int i=0;i<size;i++)
	{
		int to=g[now][i].to;
		int len=g[now][i].cap;
		int f=g[now][i].flink;
		if(!vis[to] && len>0)
		{
			int v=dfs(to,aim,min(len,val));
			if(v>0)
			{
				g[now][i].cap-=v;
				g[to][f].cap+=v;
				return v;
			}
		}
	}
	return 0;
}
int EK()
{
	int ans=0;
	while(1)
	{
		memset(vis,0,sizeof(vis));
		int flow=dfs(st,ed,INF);
		if(!flow)
			return ans;
		ans+=flow;
	}
	return ans;
}
int main()
{
	scanf("%d %d %d %d",&m,&n,&st,&ed);
	for(int i=0;i<m;i++)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		g[a].push_back(node(b,c,g[b].size()));
		g[b].push_back(node(a,0,g[a].size()-1));
	}
	printf("%d\n",EK());
	return 0;
}

# 三、最小费用最大流

这部分用的是增广路算法，代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N=100001;
const int INF=0x7f7f7f7f;
struct node
{
	int to;
	int len;
	int flink;
	int cost;
	node(int tt,int ll,int ff,int oo)
	{
		to=tt,len=ll,flink=ff,cost=oo;
	}
	node()
	{
	}
};
vector <node > g[N];
bool flag[N];
int n,m,S,T,dis[N],flow[N],pre[N][2];
bool spfa()
{
	memset(pre,0,sizeof(pre));
	memset(dis,0x3f,sizeof(dis));
	memset(flow,0x3f,sizeof(flow));
	memset(flag,0,sizeof(flag));
	queue <int > q;
	q.push(S),dis[S]=0,pre[T][0]=-1,flag[S]=true;
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		flag[t]=false;
		int size=g[t].size();
		for(int i=0;i<size;i++)
		{
			int to=g[t][i].to;
			int len=g[t][i].len;
			int cos=g[t][i].cost;
			if(len>0 && dis[to]>dis[t]+cos)
			{
				dis[to]=dis[t]+cos;
				flow[to]=min(flow[t],len);
				pre[to][0]=t;
				pre[to][1]=i;
				if(!flag[to])
					q.push(to),flag[to]=true;
			}
		}
	}
	return dis[T]!=0x3f3f3f3f;
}
int maxflow,mincost;
void MDMF()
{
	while(spfa())
	{
		int now=T;
		maxflow+=flow[T];
		mincost+=flow[T]*dis[T];
		while(now!=S)
		{
			g[pre[now][0]][pre[now][1]].len-=flow[T];
			g[now][g[pre[now][0]][pre[now][1]].flink].len+=flow[T];
			now=pre[now][0];
		}
	}
	return;
}
void add(int now,int to,int len,int cos)
{
	g[now].push_back(node(to,len,g[to].size(),cos));
	g[to].push_back(node(now,0,g[now].size()-1,-cos));
	return;
}
int main()
{
	scanf("%d %d %d %d",&n,&m,&S,&T);
	for(int i=0;i<m;i++)
	{
		int a,b,c,d;
		scanf("%d %d %d %d",&a,&b,&c,&d);
		add(a,b,c,d);
	}
	MDMF();
	printf("%d %d\n",maxflow,mincost);
	return 0;
}

例题如下：

最小费用最大流

两种算法的具体解析请移步另一篇文章