题目描述 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 Description
n文件的第一行是一个整数n（n≤100）。信和信封依次编号为1，2，…，n。
n接下来的各行中每行有2个数i和j，表示第i封信肯定不是装在第j个信封中。文件最后一行是2个0，表示结束。
输出描述 Output Description
输出文件的各行中每行有2个数i和j，表示第i封信肯定是装在第j个信封中。请按信的编号i从小到大顺序输出。若不能确定正确装入信封的任何信件，则输出“none”。
样例输入 Sample Input
3
1 2
1 3
2 1
0 0
样例输出 Sample Output
1 1
数据范围及提示 Data Size & Hint
分类标签 Tags 点此展开
题解：
二分图匹配＋匈牙利算法
先跑二分图，判断能匹配的个数，如果不足n个，直接输出无解。然后依次删除每一条匹配好的边，判断剩余的图中能否时这条被删的匹配边的两个端点连接，若不能找到增广路，则这条边时必须保留的，输出这条边。如果一条边都没有输出，则输出无解。
程序中:
BF[i] 为 第i个信封对应第BF[i]个信
BF1[i] 为 第i个信对应第BF1[i]个信封
f[i][j] 为 第i个信可能装到第j个信封中
这道题要用BF1[]的原因是，题目要求按信的从小到大的顺序输出。每次删边时必须用BF1[]。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,BF[110],BF1[110]; 4 bool f[110][110]; 5 bitset<110> vis; 6 int Xyl(int x) 7 { 8 int i; 9 for(i=1;i<=n;i++) 10 { 11 if(f[x][i]==false&&vis[i]==0) 12 { 13 vis[i]=1; 14 if(Xyl(BF[i])==1||BF[i]==0)//BF[i]为第i个信封对应第BF[i]个信,但f[i][j]为第i个信对应第j个信封,所以要存BF1[]. 15 { 16 BF[i]=x; 17 BF1[x]=i; 18 return 1; 19 } 20 } 21 } 22 return 0; 23 } 24 int main() 25 { 26 int i,ans,U,V,tmp,tmp1,pd=0; 27 scanf("%d",&n); 28 while(1) 29 { 30 scanf("%d %d",&U,&V);if(U==0&&V==0)break; 31 f[U][V]=true; 32 } 33 ans=0; 34 memset(BF,0,sizeof(BF)); 35 for(i=1;i<=n;i++) 36 { 37 vis.reset(); 38 ans+=Xyl(i); 39 } 40 if(ans!=n)printf("none"); 41 else 42 { 43 for(i=1;i<=n;i++) 44 { 45 //if(BF[i]!=0) 46 { 47 V=BF1[i]; 48 f[i][V]=true; 49 BF1[i]=0;BF[V]=0; 50 vis.reset(); 51 if(Xyl(i)==0){printf("%d %d ",i,V);pd=1;BF1[i]=V;BF[V]=i;} 52 //BF[i]=tmp; 53 f[i][V]=false; 54 } 55 } 56 if(pd==0)printf("none"); 57 } 58 return 0; 59 }