90pts代码求调
查看原帖
90pts代码求调
978312
Gyc_Fisher楼主2023/11/3 10:05
#include <bits/stdc++.h>
#define MAXN 1000010
#define INF 0x3f3f3f3f
using namespace std;
int r,c,d;
int S,T; 
struct Edge{
	int nxt,to,val;
}edge[MAXN<<1];
int head[MAXN],tot;
inline void add_edge(int u,int v,int val){
	edge[++tot].to=v;
	edge[tot].val=val;
	edge[tot].nxt=head[u];
	head[u]=tot;
}
queue<int>q;
int lev[MAXN];
int now[MAXN];
bool bfs(){
	memset(lev,0,sizeof(lev));
	lev[S]=1;
	q.push(S);
	now[S]=head[S];
	while(!q.empty()){
		int a=q.front();
		q.pop();
		for(int i=head[a];i;i=edge[i].nxt){
			int v=edge[i].to;
			if(!lev[v]&&edge[i].val){
				now[v]=head[v];
				lev[v]=lev[a]+1;
				q.push(v);
			}
		}
	}
	return lev[T];
}
int dfs(int x,int flow){
	if(x==T) return flow;
	int maxn=flow,val=0;
	for(int i=now[x];i&&maxn;i=edge[i].nxt){
		now[x]=i;
		int v=edge[i].to;
		if(lev[v]!=lev[x]+1||!edge[i].val) continue;
		val=dfs(v,min(maxn,edge[i].val));
		if(!val) lev[v]=0;
		edge[i].val-=val;
		edge[i^1].val+=val;
		maxn-=val;
	}
	return flow-maxn;
}
int sum,ans;
int main(){
	scanf("%d%d%d",&r,&c,&d);
	tot=1;
	int id=1;
	S=id;
	int N=r*c;
	T=r*c*2+S+1;
	for(int i=1;i<=r;i++){
		char rol[25];
		scanf("%s",rol+1);
		for(int j=1;j<=c;j++){
			++id;
			int val=rol[j]-'0';
			add_edge(id,id+N,val);
			add_edge(id+N,id,0);
			if(i-d<1||j-d<1||j+d>c||i+d>r){
				add_edge(id+N,T,INF);
				add_edge(T,id+N,0);
			}
			for(int p=i;p<=min(i+d,r);p++){
				for(int h=j;h<=min(j+d,c);h++){
					if(h==j&&p==i) continue;
					if(d*d>=(i-p)*(i-p)+(h-j)*(h-j)){
						add_edge(id+N,(p-1)*c+h+S,INF);
						add_edge((p-1)*c+h+S,id+N,0);
						add_edge((p-1)*c+h+S+N,id,INF);
						add_edge(id,(p-1)*c+h+S+N,0);
					}
					else break;
				}
			}
		}
	}
	id=1;
	for(int i=1;i<=r;i++){
		char rol[25];
		scanf("%s",rol+1);
		for(int j=1;j<=c;j++){
			++id;
			if(rol[j]=='L'){
				sum++;
				add_edge(S,id,1);
				add_edge(id,S,0);
			}
		}
	}
	int perans=0;
	while(bfs()){
		while(perans=dfs(S,INF)) ans+=perans;
	}
	printf("%d",sum-ans);
	return 0;
}
2023/11/3 10:05
加载中...