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 |
一直WA求大神指正#include<cstdio> #include<cstring> using namespace std; struct linked { int value; int next; }; linked ljb[50025]; int head[50000]; int kk; void create(int n) { for(int i=1;i<=n;i++) head[i]=0; kk=1; } void add(int at,int val) { ljb[kk].value=val; ljb[kk].next=head[at]; head[at]=kk++; } bool visit[1050]; int link[1050]; int map[40][40]; int m,n,k,tm,tn; int find(int num) { for(int i=head[num];i!=0;i=ljb[i].next) { if(!visit[ljb[i].value]) { visit[ljb[i].value]=true; if(link[ljb[i].value]==-1||find(link[ljb[i].value])) { link[ljb[i].value]=num; return 1; } } } return 0; } int main() { int x,y; while(scanf("%d%d%d",&m,&n,&k)!=EOF) { create(m*n); memset(map,-1,sizeof(map)); memset(link,-1,sizeof(link)); tm=tn=0; for(int i=1;i<=k;i++) { scanf("%d%d",&x,&y); map[y][x]=0; } for(int r=1;r<=m;r++) for(int c=1;c<=n;c++) { if((r+c)%2&&map[r][c]!=0) map[r][c]=++tm; else if((r+c)%2==0&&map[r][c]!=0) map[r][c]=++tn; } for(int r=1;r<=m;r++) for(int c=1;c<=n;c++) { if((r+c)%2==0&&map[r][c]!=0) { if(r+1<=m&&map[r+1][c]!=0) add(map[r][c],map[r+1][c]); if(c+1<=n&&map[r][c+2]!=0) add(map[r][c],map[r][c+1]); if(r-1>0&&map[r-1][c]!=0) add(map[r][c],map[r-1][c]); if(c-1>0&&map[r][c-1]!=0) add(map[r][c],map[r][c-1]); } } int sum=0; for(int i=1;i<=tn;i++) { memset(visit,false,sizeof(visit)); if(find(i)) sum++; } if(sum*2==m*n-k) printf("YES\n"); else printf("NO\n"); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator