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

Re 对的,这样看是否存在一个完备匹配;

Posted by yuanchuanshun at 2012-03-18 09:50:14 on Problem 2446
In Reply To:把点分成奇偶两个集合 这样用二分匹配去做应该比较简单 Posted by:Heng_Xing at 2011-08-11 21:31:42
> #include<stdio.h>
> #include<iostream>
> #include<vector>
> using namespace std;
> typedef struct node
> {
> 	int x,y;
> }node;
> int p[33][33];
> int visit[33][33];
> node link[33][33];
> int n,m,k;
> int num;
> int f[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
> 
> int dfs(int i,int j)
> {
> 	int k;
> 	int x,y;
> 	for(k=0;k<4;k++)
> 	{
> 		x=i+f[k][0];
> 		y=j+f[k][1];
> 		if(x>=1&&x<=n&&y>=1&&y<=m)
> 		{
> 			if(!p[x][y]&&!visit[x][y])
> 			{
> 				visit[x][y]=1;
> 				if((link[x][y].x==-1&&link[x][y].y==-1)||dfs(link[x][y].x,link[x][y].y))
> 				{
> 					link[x][y].x=i;
> 					link[x][y].y=j;
> 					return 1;
> 				}
> 			}
> 		}
> 	}
> 	return 0;
> }
> 
> int func()
> {
> 	int i,j;
> 	memset(link,-1,sizeof(link));
> 	for(i=1;i<=n;i++)
> 	{
> 		for(j=1;j<=m;j++)
> 		{
> 			if(!p[i][j])
> 			{
> 				if((n%2==1&&((i-1)*n+j)%2==1)||(n%2==0&&((i%2)==(j%2))))
> 				{
> 					memset(visit,0,sizeof(visit));
> 					if(dfs(i,j))
> 					num++;
> 				}
> 			}
> 		}
> 	}
> 	if(2*num+k==n*m)
> 		return 1;
> 	else
> 		return 0;
> }
> 
> int main (void)
> {
> 	int i;
> 	int x,y;
> 	int flag;
> 	scanf("%d %d %d",&n,&m,&k);
> 	if((n*m-k)%2)
> 	{
> 		printf("NO\n");
> 		return 1;
> 	}
> 	for(i=1;i<=k;i++)
> 	{
> 		scanf("%d %d",&y,&x);
> 		p[x][y]=1;
> 	}
> 	flag=func();
> 	if(flag)
> 		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