题目: http://codevs.cn/problem/1222/

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

数据范围及提示 Data Size & Hint
 

分类标签 Tags 点此展开

题解:

二分图匹配+匈牙利算法

先跑二分图,判断能匹配的个数,如果不足n个,直接输出无解。然后依次删除每一条匹配好的边,判断剩余的图中能否时这条被删的匹配边的两个端点连接,若不能找到增广路,则这条边时必须保留的,输出这条边。如果一条边都没有输出,则输出无解。

程序中:

BF[i] 为 第i个信封对应第BF[i]个信

BF1[i] 为 第i个信对应第BF1[i]个信封

f[i][j] 为 第i个信可能装到第j个信封中

这道题要用BF1[]的原因是,题目要求按信的从小到大的顺序输出。每次删边时必须用BF1[]。

 #include<bits/stdc++.h>
using namespace std;
int n,BF[],BF1[];
bool f[][];
bitset<> vis;
int Xyl(int x)
{
int i;
for(i=;i<=n;i++)
{
if(f[x][i]==false&&vis[i]==)
{
vis[i]=;
if(Xyl(BF[i])==||BF[i]==)//BF[i]为第i个信封对应第BF[i]个信,但f[i][j]为第i个信对应第j个信封,所以要存BF1[].
{
BF[i]=x;
BF1[x]=i;
return ;
}
}
}
return ;
}
int main()
{
int i,ans,U,V,tmp,tmp1,pd=;
scanf("%d",&n);
while()
{
scanf("%d %d",&U,&V);if(U==&&V==)break;
f[U][V]=true;
}
ans=;
memset(BF,,sizeof(BF));
for(i=;i<=n;i++)
{
vis.reset();
ans+=Xyl(i);
}
if(ans!=n)printf("none");
else
{
for(i=;i<=n;i++)
{
//if(BF[i]!=0)
{
V=BF1[i];
f[i][V]=true;
BF1[i]=;BF[V]=;
vis.reset();
if(Xyl(i)==){printf("%d %d\n",i,V);pd=;BF1[i]=V;BF[V]=i;}
//BF[i]=tmp;
f[i][V]=false;
}
}
if(pd==)printf("none");
}
return ;
}
04-21 04:08