| ||||||||||
| 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