RE3个,T掉1个,求调
查看原帖
RE3个,T掉1个,求调
763878
Jerry_heng楼主2023/8/4 17:53
#include<bits/stdc++.h>
using namespace std;
const int mx=210*210,inf=INT_MAX;
int head[mx],n,m,k,sum,s,x,y,t,cnt;
bool a[201][201];
int deep[mx],cur[mx];
int d[8][2]={{1,3},{-1,3},{1,-3},{-1,-3},{3,1},{3,-1},{-3,-1},{-3,1}};
struct node{
	int to,nxt,w;
}edge[mx<<1];
void add(int u,int v){
	edge[cnt].to=v;
	edge[cnt].nxt=head[u];
	edge[cnt].w=1;
	head[u]=cnt;
	cnt++;
	edge[cnt].to=u;
	edge[cnt].nxt=head[v];
	edge[cnt].w=0;
	head[v]=cnt;
	cnt++;
}
bool bfs(){
	memset(deep,0,sizeof deep);
	memcpy(cur,head,sizeof head);
	queue<int>q;
	q.push(s);
	deep[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		if(u==t)break;
		for(int i=head[u];~i;i=edge[i].nxt){
			int v=edge[i].to;
			if(deep[v]||!edge[i].w)continue;
			deep[v]=deep[u]+1;
			q.push(v);
		}
	}
	return deep[t];
}
int dfs(int now,int f){
	int flow=0;
	if(now==t)return f;
	for(int i=cur[now];~i;i=edge[i].nxt){
		int v=edge[i].to;
		cur[now]=i;
		if(deep[v]!=deep[now]+1||edge[i].w==0)continue;
		int c=dfs(v,min(edge[i].w,f));
		if(c==0)deep[v]=0;
		else{
			f-=c,flow+=c;
			edge[i].w-=c,edge[i^1].w+=c;
		}
	}
	return flow;
}
int dinic(){
	int ans=0;
	while(bfs()){
		ans+=dfs(s,inf);
	}
	return ans;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	memset(head,-1,sizeof head);
	s=0,t=n*m+1,sum=n*m;
	for(int i=1;i<=k;i++){
		scanf("%d%d",&x,&y);
		if(!a[x][y])sum--;
		a[x][y]=1;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			if(i&1)add(s,(i-1)*m+j);
			else add((i-1)*m+j,t);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if((i&1)&&!a[i][j]){
				for(int p=0;p<8;p++){
					int x=i+d[p][0],y=j+d[p][1];
					if(0<x&&x<=n&&0<y&&y<=m&&!a[x][y]){
						add((i-1)*m+j,(x-1)*m+y);
					}
				}
			}
	printf("%d",sum-dinic());
	return 0;
}
2023/8/4 17:53
加载中...