poj 1719 Shooting Contest

                                                                                                                Shooting Contest

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 4127	Accepted: 1516	Special Judge

Description

Welcome to the Annual Byteland Shooting Contest. Each competitor will shoot to a target which is a rectangular grid. The target consists of r*c squares located in r rows and c columns. The squares are coloured white or black. There are exactly two white squares and r-2 black squares in each column. Rows are consecutively labelled 1,..,r from top to bottom and columns are labelled 1,..,c from left to right. The shooter has c shots.

A volley of c shots is correct if exactly one white square is hit in each column and there is no row without white square being hit. Help the shooter to find a correct volley of hits if such a volley exists.

Example

Consider the following target:

Volley of hits at white squares in rows 2, 3, 1, 4 in consecutive columns 1, 2, 3, 4 is correct.

Write a program that: verifies whether any correct volley of hits exists and if so, finds one of them.

Input

The first line of the input contains the number of data blocks x, 1 <= x <= 5. The following lines constitute x blocks. The first block starts in the second line of the input file; each next block starts directly after the previous one.

The first line of each block contains two integers r and c separated by a single space, 2 <= r <= c <= 1000. These are the numbers of rows and columns, respectively. Each of the next c lines in the block contains two integers separated by a single space. The integers in the input line i + 1 in the block, 1 <= i <= c, are labels of rows with white squares in the i-th column.

Output

For the i-th block, 1 <= i <= x, your program should write to the i-th line of the standard output either a sequence of c row labels (separated by single spaces) forming a correct volley of hits at white squares in consecutive columns 1, 2, ..., c, or one word NO if such a volley does not exists.

Sample Input

2
4 4
2 4
3 4
1 3
1 4
5 5
1 5
2 4
3 4
2 4
2 3
      

Sample Output

2 3 1 4
NO      

題目大意：給你一個r*c的矩陣，然後這個矩陣每一列有兩個格子是白色的，然後你在每列上開一槍，可以打這列的任意的白色格子，問你能否消除全部的行，如果包括所有行輸出你在1-c列打搶的格子的行，當然這可以是不唯一的，記好！！！是不唯一！！！！

如果打不到就輸出NO
 題目首先給出有幾組資料，對于每組資料第一行代表r和c，接下來c行有兩個數，代表這行的哪兩列是白色格子

 

解題思路：和以前那個經典的二分比對差不多，就是在一行打一槍可以消滅所有行那個題目，很容易想到二分比對，我們将白色格子的行指向列，然後求最大比對，用行去比對列，看是否能夠得到的比對數是r，如果是r的話則代表所有的行都可以被打到，然後每列對應的行，如果比對數不是r就輸出NO
 當然有特例，如果r>c，這種情況開c搶根本不可能達到r行，是以直接輸出NO

代碼：

 
       
#include<stdio.h>
#include<string.h>

bool map[1005][1005];
bool used[1005];
int link[1005];
int n,m;

bool dfs(int u)//尋找增廣路！ 找到傳回1，否則傳回0！
{
	int i;
	for(i=1;i<=m;i++)
	{
		if(map[u][i]&&!used[i])])//與x相連點，并且沒有周遊到  
		{
			used[i]=true;;//标記為周遊過 
			if(link[i]==-1||dfs(link[i]))//i 點 沒有和另一部分比對或 和i配對的點 沒有比對！ 
			{
				link[i]=u;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	int i,j,x,y,t,num;
	scanf("%d",&t);
	while(t--)
	{
		num=0;
		scanf("%d%d",&n,&m);
		memset(map,0,sizeof(map));
		memset(link,-1,sizeof(link));
		if(n>m)//行大于列 
		{
			printf("NO\n");
			continue;
		}
		for(i=1;i<=m;i++)//建圖 
		{
			scanf("%d%d",&x,&y);
			map[x][i]=true;
			map[y][i]=true;
		}
		for(i=1;i<=n;i++)
		{
			memset(used,0,sizeof(used));
			if(dfs(i))
				num++;
		}
		if(num<n)//不是完美比對 
		{
			printf("NO\n");
			continue;
		}
		else
		{
			for(i=1;i<=m;i++)
			{
				if(link[i]!=-1) 
					printf("%d ",link[i]);
				else
				{
					for(j=1;j<=n;j++)
						if(map[j][i])
						{
							printf("%d ",j);
							break;
						}
				}
			}
			printf("\n");
		}
	}
	return 0;
}