Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

nail-biting WA

Posted by Santana at 2008-09-06 17:05:11 on Problem 1719
//每一行看至少有一个白格,从每一列看有且仅有一个白格被射中
//也就是说为每一行匹配一个列,其余的列随意指定

#include <iostream>
using namespace std;

#define M 1010
int r,c;
bool used[M],square[M][M];
int link[M];
int white[M]; //每列有两个白格,记录其中一个的行标,以便最后随意指定未匹配列的行标
//对于匹配了的列,记录对应的行标
void Initial()
{
	memset( square, 0, sizeof(square) );
	memset( link, -1, sizeof(link) );
}

void In()
{
	cin>>r>>c;
	for(int i=1; i<=c; i++){
		int j1,j2;
		scanf("%d%d", &j1,&j2);
		square[j1][i] = square[j2][i] = true;
		white[i] = j1;
	}
}

int find(int t)
{
	for(int i=1; i<=c; i++){
		if( !used[i] && square[t][i] ){
			used[i] = true;
			if( link[i]==-1 ){
				link[i] = t;
				return i;
			}
			int temp = find( link[i] );
			if( temp )
				return temp;
		}
	}
	return 0;
}

void solve()
{
	int cnt=0;
	for(int i=1; i<=r; i++){
		memset( used, 0, sizeof(used) );
		int temp = find(i);
		if( temp ){
			white[ temp ] = i;
			++cnt;
		}
	}

	if(cnt==r){
		for(int i=1; i<=r; i++)
			printf("%d ", white[i]);
		printf("\n");
	}
	else
		printf("NO\n");
}

int main()
{
	int Case;
	cin>>Case;
	while(Case--){
		Initial();
		In();	
		solve();
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator