首页 > 代码库 > codevs1222 信与信封问题
codevs1222 信与信封问题
1222 信与信封问题
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 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
/*开始把边取反，然后跑一边匈牙利算法，然后判断是不是完美匹配（概念网上自己去找），不是就直接输出none；第二步每次删掉一条边，判断是不是完美匹配，不是就输出这个两个点；第二步跑完之后没有发现有一个是可以输出的，就输出none；*/#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#define N 555using namespace std;int mx[N],Li[N],head[N];int n,cut_x,cut_y,S[N],T[N],num,flag=0;bool vis[N],k[N][N];struct node{ int u; int to; int next;} e[N<<1];void add(int u,int to){ e[++num].to=to;e[num].next=head[u];head[u]=num;}int dfs(int x){ int v; for (int i=head[x];i!=0;i=e[i].next) { v=e[i].to; if(x==cut_x && v==cut_y) continue; if(vis[v]==true) continue; vis[v]=true; if(Li[v]==0 || dfs(Li[v]) ) { mx[x]=v; Li[v]=x; return 1; } } return 0;}int maxmatch(){ int ans=0; for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) vis[j]=false; ans+=dfs(i); } return ans;}void Impotant_edge(){ int ans; for (int i=1;i<=n;i++) { S[i]=i;T[i]=mx[i]; } for (int i=1;i<=n;i++) { cut_x=S[i];cut_y=T[i]; for (int j=1;j<=n;j++) mx[j]=0,Li[j]=0; ans=maxmatch(); if (ans!=n) { printf("%d %d\n",cut_x,cut_y); flag=1; } } return;}int main(){ int ans,x,y; scanf("%d",&n); while(1) { scanf("%d%d",&x,&y); if (x==0&&y==0) break; k[x][y]=1; } for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if( k[i][j]==0 ) add(i,j); ans=maxmatch(); if (ans!=n) { cout<<"none"<<endl; return 0; } else { Impotant_edge(); if (flag==0) cout<<"none"<<endl; return 0; }}
codevs1222 信与信封问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。