「网络流24题」飞行员配对方案问题

发表于 | 分类于 | | 浏览量： 次

没啥好说的，就是二分图的最大匹配

传送门

洛谷P2756

LOJ6000

输入输出格式有所不同。

题解

就是一个二分图的最大匹配问题啊，裸的一批，直接上匈牙利搞就好了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=105;
int n,m,tot,lnk[maxn],son[maxn*maxn],nxt[maxn*maxn],cp[maxn],ans;bool vis[maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void add_e(int x,int y){tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
bool Hungary(int now)
{
	for(int i=lnk[now];i;i=nxt[i])
	{
		if(!vis[son[i]])
		{
			vis[son[i]]=true;
			if(!cp[son[i]]||Hungary(cp[son[i]]))
			{
				cp[son[i]]=now;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	m=read();n=read();
	while(true)
	{
		int a=read(),b=read()-m;
		if(a<0&&b<0) break;
		add_e(b,a);
	}
	for(int i=1;i<=n;i++)
	{
		memset(vis,false,sizeof(vis));
		ans+=Hungary(i);
	}
	if(ans==0){printf("No Solution!\n");return 0;}
	printf("%d\n",ans);
	for(int i=1;i<=m;i++)
		if(cp[i])
			printf("%d %d\n",i,cp[i]+m);
	return 0;
}