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

汗....就因为开小了一个数组 贡献了N多RTE.......这题过的挺莫名其妙........

Posted by solopointer at 2010-09-24 00:27:03 on Problem 3020
#include <stdio.h>

int map[45][15];
int arcs[405][405];
int visiting[450];
int match[450];


int N;
int h,w;
int num;
int dir[4][2]={{0,-1},{0,1},{-1,0},{1,0},};

int find(int k)
{

	int a;
	for(a=1;a<=num;a++)
		if(arcs[k][a]&&!visiting[a])
			if(!match[a]||(visiting[a]=1,find(match[a])))
			{
				match[a]=k,match[k]=a;
				return 1;
			}
	return 0;
}
int calc()
{
	int a,b;
	int result;
	result=0;

	for(a=1;a<=num;a++)
		match[a]=0;
	for(a=1;a<=num;a++)
	{
		for(b=1;b<=num;b++)
			visiting[b]=0;
		if(!match[a]&&find(a))
			result++;
	}
	return result;
}
void main()
{
	int a,b;
	int i;
	char ch;
	scanf("%d",&N);
	while(N)
	{
		num=0;
		scanf("%d%d",&h,&w);
		for(a=1;a<=h;a++)
		{
			for(b=1;b<=w;b++)
			{
				scanf("\n%c",&ch);
				map[a][b]=(ch=='*'?++num:0);
			}
			
		}
		for(a=0;a<=w+1;a++)
			map[0][a]=map[h+1][a]=0;
		for(a=0;a<=h+1;a++)
			map[a][0]=map[a][w+1]=0;
		for(a=1;a<=num;a++)
			for(b=1;b<=num;b++)
				arcs[a][b]=0;

		for(a=1;a<=h;a++)
			for(b=1;b<=w;b++)
				if(map[a][b])
					for(i=0;i<4;i++)
						if(map[a+dir[i][0]][b+dir[i][1]])
							arcs[map[a][b]][map[a+dir[i][0]][b+dir[i][1]]]=arcs[map[a+dir[i][0]][b+dir[i][1]]][map[a][b]]=1;

		printf("%d\n",num-calc());
		--N;
	}

}


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