「CODEVS1222」信与信封问题
题目描述 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
题解
这是一道二分图匹配的变式,假如一条边不可获缺,那么没有它一定无法完美匹配,由此可以推得先进行一次匹配,再对匹配的边依次删除,如果不能完美匹配就输出
|
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 51 52 |
#include<cstdio> #include<cstring> bool del[101][101]; int vis[101],lky[101],lkx[101]; int n,ans; bool find(int u) { for(int i=1;i<=n;i++) if(!del[u][i]&&!vis[i]) { vis[i]=1; if(!lky[i]||find(lky[i])) { lky[i]=u; lkx[u]=i; return 1; } } return 0; } int main() { scanf("%d",&n); int x,y; while(scanf("%d%d",&x,&y)&&x&&y) del[x][y]=1; for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(find(i))ans++; } if(ans!=n)printf("none"); else { bool flag=0; for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); int t=lkx[i]; del[i][t]=1; lky[t]=0;lkx[i]=0; if(!find(i)) { printf("%d %d\n",i,t); lkx[i]=t;lky[t]=i;flag=1; } del[i][t]=0; } if(!flag)printf("none"); } return 0; } |
Subscribe
计数器 9787343
OI 课件=>
OI 课件=>