poj 1719Shooting Contest
//本題大意是對於一個r*c的矩陣，每一列有兩個是白色的
//現在選c個位置，要求每一行至少有一個白色的方格被選上
//每一列只能選一個
//用二分匹配求出最大匹配，如果最大匹配等於r,則滿足
//每一行至少有一個白色的格子被選上
//注意c>r的情況
#include
#include
#include
using namespace std;
const int maxn = 1010;
int line[maxn][maxn];
int match[maxn];
int match_ans[maxn];
int vis[maxn];
int r,c;
int find(int start)
{
int i ;
for(i=1;i<=r;i++)
{
if(line[start][i]&&!vis[i])
{
vis[i]=1;
if(match[i]==-1||find(match[i]))
{
match[i] = start ;
match_ans[start] = i;
return 1;
}
}
}
return 0;
}
void Match()
{
int i;
memset(match , -1 ,sizeof(match));
int ans = 0;
for(i = 1; i <= c;i++)
{
memset(vis , 0 , sizeof(vis));
if(find(i))
ans++;
}
if(ans == r)
{
for(i = 1;i <= c; i++)
{
if(!match_ans[i])
{
for(int j = 1;j <= r ;j++)
if(line[i][j])
{
printf("%d%c",j,i == c?'\n':' ');
break;
}
}
else
printf("%d%c",match_ans[i],i == c?'\n':' ');
}
}
else
printf("NO\n");
}
int main()
{
//freopen("in.txt", "r" ,stdin);
int T;
scanf("%d", &T);
while(T--)
{
memset(line, 0 ,sizeof(line));
memset(match_ans , 0 ,sizeof(match_ans));
scanf("%d%d" ,&r , &c);
int a,b;
for(int i = 1; i <= c ;i++)
{
scanf("%d%d",&a ,&b);
line[i][a] = line[i][b] = 1;
}
Match();
}
return 1;
}
