完美匹配问题
Problem Description
John先生晚上写了n封信，并相应地写了n个信封将信装好，准备寄出。但是，第二天John的儿子Small John将这n封信都拿出了信封。不幸的是，Small John无法将拿出的信正确地装回信封中了。
编程任务
将Small John所提供的n封信依次编号为1,2,...,n; 且n个信封也依次编号为1,2,...,n。假定Small John能提供一组信息：第i封信肯定不是装在信封j中。请编程帮助Small John，尽可能多地将信正确地装回信封。
Input
本题有多组输入数据，你必须处理到EOF为止。
每组数据的第一行是一个整数n（n≤100）。信和信封依次编号为1,2,…,n。
接下来的各行中每行有2个数i和j，表示第i封信肯定不是装在第j个信封中。输入最后一行是2个0，表示结束。
Output
对于每组数据，输出的各行中每行有2个数i和j，表示第i封信肯定是装在第j个信封中。请按信的编号i从小到大顺序输出。若不能确定正确装入信封的任何信件，则输出“none”。
每组输出结束之后，输出一个空行。
#include<iostream>#include<cstdio>#include<cstdlib>#include<memory.h>using namespace std;int v[101], n;int map[101][101];int l[101], f[101];bool find(int x){ for(int i=1;i<=n;++i){ if(!map[x][i] && !v[i]){ v[i] = 1; if(l[i]==0 || find(l[i])){ l[i] = x; return true; } } } return false;}int hungary(){ memset(l, 0, sizeof(l)); int ans = 0; for(int i=1;i<=n;++i){ memset(v, 0, sizeof(v)); if(find(i)) ans++; } return ans;}int main(){ freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); int s1,s2; while(cin>>n){ memset(map, 0, sizeof(map)); while(cin>>s1>>s2, s1+s2) map[s1][s2] = 1; int should = hungary(); if(should!=n){ cout<<"none"<<endl; continue; } bool flag = false; memcpy(f, l, sizeof(l)); for(int i=1;i<=n;++i){ map[f[i]][i] = 1; if(hungary()!=should){ cout<<f[i]<<" "<<i<<endl; flag = true; } map[f[i]][i] = 0; } if(!flag) cout<<"none"<<endl; } fclose(stdin); fclose(stdout);}