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