【线性规划与网络流24题 1】飞行员配对方案

Description

第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1 名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

由于本OJ无Special Judge ，所以只需要输出最多能派出的飞机数

Input

第1 行有2个正整数m和n。n是皇家空军的飞行员总数(n<100)；m是外籍飞行员数。外籍飞行员编号为1~m；英国飞行员编号为m+1~n。
接下来每行有2 个正整数i和j，表示外籍飞行员i可以和英国飞行员j配合。
最后以2个-1 结束。

Output

程序运行结束时，将最佳飞行员配对方案输出。第 1 行是最佳飞行员配对方案一次能派出的最多的飞机数 M。
/*
接下来 M 行是最佳飞行员配对方案。
每行有 2个正整数 i和j，表示在最佳飞行员配对方案中，飞行员i和飞行员j配对。
如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’ 。
配对方案按照字典序输出
*/

Sample Input

Sample Output

这个题：

典型的二分图最大匹配，求匹配数和匹配方案的问题！

用经典hungary（）模板可以得到最大匹配数

然后，遍历linker数组，如果不等于初始化的值，说明连过线，将其输出即可

hungary（）算法的思路：

首先给我自己节点u找到一个可以匹配的v

如果v没有被匹配过，则增加一个匹配对（u，v）

代码：

for(int v=0;v<vN;v++)
    if (linker[v]!=-1)
         printf("%d %d\n",linker[v],v);

否则，可以看看v是不是可以被其他的替代一下，换个人去匹配u0，重组一下匹配关系用dfs去找，能否增加一个新的匹配

linker【v】：当前已经匹配的v，连的是哪一个

代码如下：

//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;

const int maxn=2000;
int un,vn;
int g[maxn][maxn];
int linker[maxn];
bool used[maxn];

bool dfs(int u){
	for(int v=0;v<vn;v++)
		if (g[u][v]&&!used[v]){
			used[v]=true;
			if (linker[v]==-1||dfs(linker[v])){
				linker[v]=u;
				return true;
			}
		}
	return false;
}

int hungary(){
	int res=0;
	memset(linker,-1,sizeof(linker));
	for(int u=0;u<un;u++){
		memset(used,false,sizeof(used));
		if (dfs(u)) res++;
	}
	return res;
}

int main(){
	//freopen("input.txt","r",stdin);
	int n,m,u,v;
	scanf("%d%d",&n,&m);
	un=n;vn=m-n;
	memset(g,0,sizeof(g));
	while(scanf("%d%d",&u,&v)!=EOF){
		if (u==-1) break;
		u--;v--;v-=un;
		g[u][v]=1;
	}
	printf("%d\n",hungary());
	/*
	for(int i=0;i<vn;i++)
		if (linker[i]!=-1)
		printf("%d %d\n",linker[i]+1,i+1+un);
	*/
	return 0;
}