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 555 using namespace std;
int mx[N],Li[N],head[N];
int n,cut_x,cut_y,S[N],T[N],num,flag=;
bool vis[N],k[N][N];
struct node
{
int u;
int to;
int next;
} e[N<<]; 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!=;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]== || dfs(Li[v]) )
{
mx[x]=v;
Li[v]=x;
return ;
}
}
return ;
} int maxmatch()
{
int ans=;
for (int i=;i<=n;i++)
{
for (int j=;j<=n;j++) vis[j]=false;
ans+=dfs(i);
}
return ans;
} void Impotant_edge()
{
int ans;
for (int i=;i<=n;i++)
{
S[i]=i;T[i]=mx[i];
}
for (int i=;i<=n;i++)
{
cut_x=S[i];cut_y=T[i];
for (int j=;j<=n;j++) mx[j]=,Li[j]=;
ans=maxmatch();
if (ans!=n)
{
printf("%d %d\n",cut_x,cut_y);
flag=;
}
}
return;
} int main()
{
int ans,x,y;
scanf("%d",&n);
while()
{
scanf("%d%d",&x,&y);
if (x==&&y==) break;
k[x][y]=;
}
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
if( k[i][j]== ) add(i,j);
ans=maxmatch();
if (ans!=n)
{
cout<<"none"<<endl;
return ;
}
else
{
Impotant_edge();
if (flag==) cout<<"none"<<endl;
return ;
}
}