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

从早8点开始,WA到现在也没能找出原因来,希望有心人看看我的代码,指点一下迷津,感激涕零

Posted by aliu0932 at 2009-05-13 17:27:00 on Problem 2446
#include<stdio.h>
#include<memory.h>
#define N 36
#define init(a) memset(a,0,sizeof(a))
int x[N]={0,-1,0,1,0},y[N]={0,0,-1,0,1};
int G[N][N],used[N][N],link[N][N][2];
int n,row,col;
////////////////////////////////////黑白染色,如果数量不等则查找失败
int readData()
{
	int i,j,k,t=0;
	init(G);
	for(i=1;i<=row;i++)
		for(j=1;j<=col;j++)
			if((i+j)%2)	G[i][j]=1;
			else G[i][j]=-1;
	for(k=1;k<=n;k++)	{
		scanf("%d%d",&i,&j);	
		if(G[i][j]==1)	t++;
		G[j][i]=0;
	}
	if(2*t==n)	return 1;
	else	return 0;
}
///////////////////////////////////////匈牙利算法求完美匹配
int dfs(int sx,int sy)
{
	int i,j,k,tx,ty;
	for(k=1;k<=4;k++){
		i=sx+x[k],j=sy+y[k];
		if(G[i][j]==-1&&!used[i][j])	{
			used[i][j]=1;
			tx=link[i][j][0],ty=link[i][j][1];
			link[i][j][0]=sx,link[i][j][1]=sy;
			if(!tx||dfs(tx,ty))		return 1;
			link[i][j][0]=tx,link[i][j][1]=ty;
		}
	}
	return 0;
}

int work()
{
	int i,j;
	init(link);
	for(i=1;i<=row;i++)
		for(j=1;j<=col;j++){
			init(used);
			if(G[i][j]==1&&!dfs(i,j))		return 0;//如果有一点无法被覆盖则查找失败
		}
	return 1;
}

int main()
{
	//	freopen("data.txt","r",stdin);
	while(scanf("%d%d%d",&row,&col,&n)!=EOF)	{
		if(!readData()||(row*col-n)%2||!work())////////////黑白点总数为奇数则查找失败
			printf("NO\n");
		else
			printf("YES\n");
	}
	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