80 求助
查看原帖
80 求助
793625
Pink_Cut_Tree楼主2024/4/25 10:21
#include<bits/stdc++.h>
using namespace std;
const int M=1e6+6;
#define int long long
#define inf 2147483647
struct Edge{
	int to,nxt,val;
}edges[M<<4];
int n,m,s,t,k,ans;
bool ban[M];
int dx[]={-3,-1,1,3,3,1,-1,-3},dy[]={1,3,3,1,-1,-3,-3,-1};
int num(int x,int y){
	return (x-1)*m+y;
}
bool out(int x,int y){
	return x<1||x>n||y<1||y>m;
}
int head[M],cnt=1;
void add(int u,int v,int w){
	edges[++cnt]={v,head[u],w};
	head[u]=cnt;
}
int cur[M],dep[M];
bool bfs(){
	memcpy(cur,head,sizeof head);
	for(int i=1;i<=t;i++){
		dep[i]=inf;
	}
	queue<int>Q;
	Q.push(s);
	while(!Q.empty()){
		int u=Q.front(); Q.pop();
		for(int i=head[u];i;i=edges[i].nxt){
			int v=edges[i].to;
			if(dep[v]>dep[u]+1&&edges[i].val){
				dep[v]=dep[u]+1;
				Q.push(v);
			}
		}
	}
return dep[t]!=inf;
}
int max_flow;
int dfs(int u,int flow){
	if(u==t){
		max_flow+=flow;
		return flow;
	}
	int used=0;
	for(int i=cur[u];i;i=edges[i].nxt){
		int v=edges[i].to;
		cur[u]=i;
		if(dep[v]==dep[u]+1&&edges[i].val){
			int rflow=dfs(v,min(edges[i].val,flow-used));
			if(rflow){
				used+=rflow;
				edges[i].val-=rflow;
				edges[i^1].val+=rflow;
				if(flow==used){
					return used;
				}
			}
		}
	}
return used;
}
int dinic(){
	while(bfs()){
		dfs(s,inf);
	}
return max_flow;
}
int x,y;
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m>>k;
	s=0,t=n*m+1,ans=n*m;
	while(k--){
		cin>>x>>y;
		if(!ban[num(x,y)]){
			ban[num(x,y)]=1; ans--;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i&1){
				add(s,num(i,j),1);
				add(num(i,j),s,0);
			}
			else{
				add(num(i,j),t,1);
				add(t,num(i,j),0);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(ban[num(i,j)]){
				continue;
			}
			for(int k=0;k<8;k++){
				int px=i+dx[k],py=j+dy[k];
				if(!out(px,py)&&!ban[num(px,py)]){
					add(num(i,j),num(px,py),1);
					add(num(px,py),num(i,j),0);
				}
			}
		}
	}
	cout<<ans-dinic();
return 0;
}
2024/4/25 10:21
加载中...