P4313 文理分科 RE30分 求调!!
  • 板块题目总版
  • 楼主708zz
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/7/26 09:18
  • 上次更新2023/11/3 07:37:42
查看原帖
P4313 文理分科 RE30分 求调!!
479909
708zz楼主2023/7/26 09:18
#include <bits/stdc++.h>
using namespace std;

inline int read(){
	int sum=0,f=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()){
		f |= (ch=='-');
	}
	for(;isdigit(ch);ch=getchar()){
		sum = ((sum<<3) + (sum<<1) + (ch^48));
	}
	return f?-sum:sum;
}

const int maxn = 5050;
const int inf = 0x3f3f3f3f;

int n,m,s,t,cnt=1,ans,cur[maxn],deep[maxn],head[maxn];
int art[maxn][maxn],sci[maxn][maxn],exart[maxn][maxn],exsci[maxn][maxn];
int mv[5][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

struct edge{
	int to,nxt,w;
}e[maxn];

void add(int u,int v,int w){
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}

void addedge(int u,int v,int w){
	add(u,v,w);
	add(v,u,0);
}

int node(int x,int y){
	return (x-1)*m+y;
}

int sameart(int x,int y){
	return n*m*1 + node(x,y);
}

int samesci(int x,int y){
	return n*m*2 + node(x,y);
}

bool in(int x,int y){
	return ((1<=x) && (x<=n) && (1<=y) && (y<=m));
}

bool bfs(){
	for(int i=1;i<=t;i++){
		cur[i] = head[i];
		deep[i] = inf;
	}
	queue <int> q;
	q.push(s);
	deep[s] = 0;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int i=head[u];~i;i=e[i].nxt){
			int v = e[i].to;
			if(e[i].w && (deep[v]==inf)){
				deep[v] = deep[u]+1;
				q.push(v);
			}
		}
	}
	if(deep[t] == inf){
		return false;
	}
	return true;
}

int dfs(int u,int t,int limit){
	if((u==t) || (!limit)){
		return limit;
	}
	int tmp=0,flow=0;
	for(int i=cur[u];~i;i=e[i].nxt){
		int v = e[i].to;
		if(deep[v] == deep[u]+1){
			tmp = dfs(v,t,min(limit , e[i].w));
			limit -= tmp;
			flow += tmp;
			e[i].w -= tmp;
			e[i^1].w += tmp;
			if(!limit){
				break;
			}
		}
	}
	return flow;
}

int dinic(){
	int mc=0;
	while(bfs()){
		mc += dfs(s,t,inf);
	}
	return mc;
}

int main(){
	memset(head,-1,sizeof(head));
	n=read(); m=read();
	s = n*m*3+1;
	t = n*m*3+2;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			art[i][j] = read();
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			sci[i][j] = read();
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			exart[i][j] = read();
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			exsci[i][j] = read();
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			addedge(s,node(i,j),art[i][j]);
			addedge(node(i,j),t,sci[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			addedge(s,sameart(i,j),exart[i][j]);
			addedge(samesci(i,j),t,exsci[i][j]);
			for(int k=0;k<5;k++){
				int tx = i+mv[k][0];
				int ty = j+mv[k][1];
				if(in(tx,ty)){
					addedge(sameart(i,j),node(tx,ty),inf);
					addedge(node(tx,ty),samesci(i,j),inf);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ans += art[i][j]+sci[i][j]+exart[i][j]+exsci[i][j];
		}
	}
	printf("%d",ans-dinic());
	return 0;
}
2023/7/26 09:18
加载中...