| ||||||||||
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 |
这段代码怎么CE的?自己机器上都好的#include <stdio.h> #include <memory.h> #define MAX 1000 int dx[4] = {-1,0,0,1}; int dy[4] = {0,-1,1,0}; int G[MAX][MAX],deg[MAX]; int id[MAX],used[MAX],link[MAX],cnt; int N,not[40][40]; int m,n,k; void dfs(int u) { int i,v; used[u] = 1; id[u] = cnt; cnt = 1-cnt; for(i=0;i<deg[u];i++) { v = G[u][i]; if(used[v]==0){ dfs(v); } } } bool inside(int a,int b) { return a>=0&&a<m&&b>=0&&b<n&¬[a][b]==0; } int can(int t) { int i,v; for(i=0;i<deg[t];i++) { v = G[t][i]; if(id[v]==1&&used[v]==0) { used[v] = 1; if(link[v]==-1||can(link[v])){ link[v] = t; return 1; } } } return 0; } int MaxMatch() { int i,ret=0; memset(link,-1,sizeof(link)); for(i=0;i<N;i++) { if(id[i]==0){ memset(used,0,sizeof(used)); if(can(i))ret++; } } return ret; } int main() { int i,j,t,a,b,c; while(scanf("%d%d%d",&m,&n,&k)!=EOF) { memset(not,0,sizeof(not)); c = 0; for(i=0;i<k;i++){ scanf("%d%d",&b,&a); if(not[a][b]==1)c++; else not[a][b] = 1; } k = k-c; memset(deg,0,sizeof(deg)); a = b = -1; for(i=0;i<m;i++) for(j=0;j<n;j++) { if(not[i][j])continue; if(a==-1){ a = i;b = j; } for(t=0;t<4;t++) { int tx = i+dx[t]; int ty = j+dy[t]; if(inside(tx,ty)){ G[i*n+j][deg[i*n+j]++] = tx*n+ty; G[tx*n+ty][deg[tx*n+ty]++] = i*n+j; } } } memset(id,-1,sizeof(id)); memset(used,0,sizeof(used)); cnt = 0; if(a==-1){ printf("YES\n"); continue; } dfs(a*n+b); N = n*m; int ans = MaxMatch(); if(ans*2==N-k)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