Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register

## Re:吃屎吧，数组要开到2000，血试出来的，唉

Posted by swust5120171204 at 2019-05-09 17:41:32 on Problem 2446
In Reply To:吃屎吧，数组要开到2000，血试出来的，唉 Posted by:jerrywans119 at 2018-04-04 22:20:20
```> #include<cstdio>
> #include<cstring>
>
> const int N=2000+5;
>
> using namespace std;
>
> int cnt[N][N],tag[N][N],g[N][N],link[N];
> int n,m,x,y,k,ans,cntx;
> bool vis[N];
>
> void init(){
> 	ans=0;cntx=0;
> 	memset(link,0,sizeof(link));
> 	memset(cnt,0,sizeof(cnt));
> 	memset(tag,0,sizeof(tag));
> 	memset(g,0,sizeof(g));
> }
>
> bool find(int x){
> 	int v;
> 	for(int j=1;j<=cntx;j++){
> 		if((!vis[j]) && g[x][j]){
> 			vis[j]=true;
> 			if((!link[j]) || (find(link[j]))){
> 				link[j]=x;
> 				return true;
> 			}
> 		}
> 	}
> 	return false;
> }
>
> int main(){
> 	freopen("test.in","r",stdin);
> 	while(scanf("%d%d%d",&m,&n,&k)==3){
> 		init();
> 		for(int i=1;i<=k;i++){
> 			scanf("%d%d",&y,&x);
> 			tag[x][y]=1;
> 		}
> 		for(int i=1;i<=m;i++)
> 		    for(int j=1;j<=n;j++)
> 		        if(!tag[i][j])
> 		            cnt[i][j]=++cntx;
> 		for(int i=1;i<=m;i++)
> 			for(int j=1;j<=n;j++)
> 				if(!tag[i][j]){
> 					if(j>1 && !tag[i][j-1]) g[cnt[i][j]][cnt[i][j-1]]=1;
> 					if(j<n && !tag[i][j+1]) g[cnt[i][j]][cnt[i][j+1]]=1;
> 					if(i>1 && !tag[i-1][j]) g[cnt[i][j]][cnt[i-1][j]]=1;
> 					if(i<m && !tag[i+1][j]) g[cnt[i][j]][cnt[i+1][j]]=1;
> 				}
> 		for(int i=1;i<=cntx;i++){
> 			memset(vis,false,sizeof(vis));
> 			if(find(i))
> 			    ans++;
> 		}
> 		if(ans==cntx) printf("YES\n");
> 		else printf("NO\n");
> 	}
> 	return 0;
> }
```

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator