| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re 对的,这样看是否存在一个完备匹配;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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator