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 |
出来吼吼。。。这题做的郁闷。。。贴代码。。。仅供参考。。#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> using namespace std; const int MAXN=50 ; struct node { int x,y ; }; node link[MAXN][MAXN] ; int map[MAXN][MAXN] ; int visit[MAXN][MAXN] ; int k,m,n ; int move[4][2]={0,-1,0,1,1,0,-1,0 } ; int path(int tx,int ty) { for(int i=0 ;i<4 ;i++) { int cx=tx+move[i][0] ; int cy=ty+move[i][1] ; if(cx>=1 && cx<=n && cy>=1 && cy<=m) { if(!map[cx][cy] && !visit[cx][cy]) { visit[cx][cy]=1 ; if((link[cx][cy].x==-1&&link[cx][cy].y==-1)||path(link[cx][cy].x,link[cx][cy].y)) { link[cx][cy].x=tx ; link[cx][cy].y=ty ; return 1 ; } } } } return 0 ; } int MaxMatch() { memset(link,-1,sizeof(link)) ; int res=0 ; for(int i=1 ;i<=n;i++) for(int j=1 ;j<=m ;j++) { if(!map[i][j]) { if((i+j)%2==1) { memset(visit,0,sizeof(visit)) ; if(path(i,j)) res++ ; } } } if(res*2+k==m*n) return 1 ; else return 0 ; } int main() { // freopen("in.txt","r",stdin) ; while(cin>>n>>m>>k) { if((m*n-k)%2==1) cout<<"NO"<<endl; else { memset(map,0,sizeof(map)) ; for(int i=0 ;i<k ;i++) { int cx,cy ; cin>>cy>>cx ; map[cx][cy]=1 ; } if(MaxMatch()) cout<<"YES"<<endl; else cout<<"NO"<<endl ; } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator