WA4个点(64分)求助,#7,8,9,10WA
查看原帖
WA4个点(64分)求助,#7,8,9,10WA
71947
Stupid_xyf_2楼主2021/1/2 20:54
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const long long maxn=10000;
const long long INF=0x3f3f3f3f3f3f3f;
struct Edge {
	long long from,to;
	long long cap,flow;
};
struct DICNIC {
	long long n,m,s,t;
	vector<Edge>edges;
	vector<long long>G[maxn];
	vector<Edge>ans;
	bool vis[maxn];
	long long d[maxn];
	long long cur[maxn];
	inline void AddEdge(long long from,long long to,long long cap) {
		edges.push_back((Edge) {
			from,to,cap,0
		});
		edges.push_back((Edge) {
			to,from,0,0
		});
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1);
	}
	bool BFS() {
		memset(vis,0,sizeof(vis));
		queue<long long>Q;
		Q.push(s);
		d[s]=0;
		vis[s]=1;
		while(!Q.empty()) {
			long long x=Q.front();
			Q.pop();
			for(long long i=0; i<G[x].size(); i++) {
				Edge &e=edges[G[x][i]];
				if(!vis[e.to]&&e.cap>e.flow) {
					vis[e.to]=1;
					d[e.to]=d[x]+1;
					Q.push(e.to);
				}
			}
		}
		return vis[t];
	}
	long long DFS(long long x,long long a) {
		if(x==t||a==0)return a;
		long long flow=0,f;
		for(long long &i=cur[x]; i<G[x].size(); i++) {
			Edge &e=edges[G[x][i]];
			if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0) {
				e.flow+=f;
				edges[G[x][i]^1].flow-=f;
				flow+=f;
				a-=f;
				if(a==0)break;
			}
		}
		return flow;
	}
	long long maxflow(long long s,long long t) {
		this->s=s,this->t=t;
		long long flow=0;
		while(BFS()) {
			memset(cur,0,sizeof(cur));
			flow+=DFS(s,INF);
		}
		return flow;
	}
} dic;
long long r,c,d;
long long sum=0;
long long h[30][30];
long long f[30][30];
char ch[30][30];
int main() {
	cin>>r>>c>>d;
	for(long long i=1; i<=r; i++)
		for(long long j=1; j<=c; j++)
			cin>>ch[i][j],h[i][j]=ch[i][j]-'0';
	for(long long i=1; i<=r; i++)
		for(long long j=1; j<=c; j++)
			if(h[i][j]) {
				if(i-d<=0||j-d<=0||i+d>r||j+d>c)
					dic.AddEdge(((i-1)*r+j+r*c),r*c*2+2,INF);
				dic.AddEdge(((i-1)*r+j),((i-1)*r+j+r*c),h[i][j]);
				for(long long vi=1; vi<=r; vi++)
					for(long long vj=1; vj<=c; vj++)
						if((vi!=i||vj!=j)&&h[vi][vj]>0)
							if((vi-i)*(vi-i)+(vj-j)*(vj-j)<=d*d)
								dic.AddEdge(((i-1)*r+j+r*c),((vi-1)*r+vj),INF);
			}
	for(long long i=1; i<=r; i++)
		for(long long j=1; j<=c; j++) {
			cin>>ch[i][j];
			if(ch[i][j]=='L') {
				sum++;
				dic.AddEdge(r*c*2+1,((i-1)*r+j),1);
			}
		}
	cout<<sum-dic.maxflow(r*c*2+1,r*c*2+2)<<endl;
}
2021/1/2 20:54
加载中...