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

这段代码怎么CE的?自己机器上都好的

Posted by notsure at 2008-10-27 20:35:23
#include <stdio.h>
#include <memory.h>
#define MAX 1000
int dx[4] = {-1,0,0,1};
int dy[4] = {0,-1,1,0};
int G[MAX][MAX],deg[MAX];
int id[MAX],used[MAX],link[MAX],cnt;
int N,not[40][40];
int m,n,k;
void dfs(int u)
{
	int i,v;
	used[u] = 1;
	id[u] = cnt;
	cnt = 1-cnt;
	for(i=0;i<deg[u];i++)
	{
		v = G[u][i];
		if(used[v]==0){
			dfs(v);
		}
	}
}
bool inside(int a,int b)
{
	return a>=0&&a<m&&b>=0&&b<n&&not[a][b]==0;
}
int can(int t)
{
	int i,v;
	for(i=0;i<deg[t];i++)
	{
		v = G[t][i];
		if(id[v]==1&&used[v]==0)
		{
			used[v] = 1;
			if(link[v]==-1||can(link[v])){
				link[v] = t;
				return 1;
			}
		}
	}
	return 0;
}
int MaxMatch()
{
	int i,ret=0;
	memset(link,-1,sizeof(link));
	for(i=0;i<N;i++)
	{
		if(id[i]==0){
			memset(used,0,sizeof(used));
			if(can(i))ret++;
		}
	}
	return ret;
}
int main()
{
	int i,j,t,a,b,c;
	while(scanf("%d%d%d",&m,&n,&k)!=EOF)
	{
		memset(not,0,sizeof(not));
		c = 0;
		for(i=0;i<k;i++){
			scanf("%d%d",&b,&a);
			if(not[a][b]==1)c++;
			else not[a][b] = 1;
		}
		k = k-c;
		memset(deg,0,sizeof(deg));
		a = b = -1;
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
			{
				if(not[i][j])continue;
				if(a==-1){
					a = i;b = j;
				}
				for(t=0;t<4;t++)
				{
					int tx = i+dx[t];
					int ty = j+dy[t];
					if(inside(tx,ty)){
						G[i*n+j][deg[i*n+j]++] = tx*n+ty;
						G[tx*n+ty][deg[tx*n+ty]++] = i*n+j;
					}
				}
			}
		memset(id,-1,sizeof(id));
		memset(used,0,sizeof(used));
		cnt = 0;
		if(a==-1){
			printf("YES\n");
			continue;
		}
		dfs(a*n+b);
		N = n*m;
		int ans = MaxMatch();
		if(ans*2==N-k)printf("YES\n");
		else printf("NO\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