【洛谷P2756】飞行员配对方案问题

题目大意：二分图匹配裸题。

题解：用网络流进行处理。

找配对方案的时候，采用遍历二分图左边的每个节点，找到不与源点相连，且正向边权值为 0，反向边权值为 1 的边，输出即可。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=110;

const int maxm=1e4+10;

const int inf=1<<30;

int n,m,s,t,d[maxn],maxflow;

struct node{int nxt,to,w;}e[maxm<<1];

int tot=1,head[maxn];

inline void add_edge(int from,int to,int w){

	e[++tot]=node{head[from],to,w},head[from]=tot;

	e[++tot]=node{head[to],from,0},head[to]=tot;

}

bool bfs(){

	queue<int> q;

	memset(d,0,sizeof(d));

	d[s]=1,q.push(s);

	while(q.size()){

		int u=q.front();q.pop();

		for(int i=head[u];i;i=e[i].nxt){

			int v=e[i].to,w=e[i].w;

			if(w&&!d[v]){

				d[v]=d[u]+1;

				q.push(v);

				if(v==t)return 1;

			}

		}

	}

	return 0;

}

int dinic(int u,int flow){

	if(u==t)return flow;

	int rest=flow;

	for(int i=head[u];i&&rest;i=e[i].nxt){

		int v=e[i].to,w=e[i].w;

		if(w&&d[v]==d[u]+1){

			int k=dinic(v,min(rest,w));

			if(!k)d[v]=0;

			e[i].w-=k,e[i^1].w+=k,rest-=k;

		}

	}

	return flow-rest;

}

void read_and_parse(){

	int x,y;

	scanf("%d%d",&m,&n);

	while(scanf("%d%d",&x,&y)&&x!=-1)add_edge(x,y,1);

	for(int i=1;i<=m;i++)add_edge(0,i,1);

	for(int i=m+1;i<=n;i++)add_edge(i,n+1,1);

	s=0,t=n+1;

}

void solve(){

	while(bfs())while(int now=dinic(s,inf))maxflow+=now;

	if(maxflow==0)return (void)puts("No Solution!");

	printf("%d\n",maxflow);

	for(int u=1;u<=m;u++)

		for(int i=head[u];i;i=e[i].nxt)

			if(e[i].to!=s&&e[i].w==0&&e[i^1].w==1)

				printf("%d %d\n",u,e[i].to);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【洛谷P2756】飞行员配对方案问题

最新文章

热门文章