萌新求助,RE30分
查看原帖
萌新求助,RE30分
164883
Zigh_Wang楼主2022/8/18 17:43
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int MAXN = 100 + 5;
const int MAXP = MAXN * MAXN * 400;
const int MAXE = MAXP * 10;
const int INF = 0x3f3f3f3f;

int inpt()
{
	int x = 0, f = 1;
	char ch;
	for(ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
	if(ch == '-'){
		f = -1;
		ch = getchar();
	}
	do{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}while(ch >= '0' && ch <= '9');
	return x * f;
}

int n, m;
ll ans = 0;
int art[MAXN][MAXN], sci[MAXN][MAXN];
int same_art[MAXN][MAXN], same_sci[MAXN][MAXN];

struct Edge {
	int hd[MAXP];
	int nxt[MAXE], to[MAXE];
	int w[MAXE];
	int now[MAXE];
	int tot = 1;
	
	void Add(int x, int y, int z) {
		nxt[++tot] = hd[x];
		hd[x] = tot;
		to[tot] = y;
		w[tot] = z;
	}
}e;

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

int ext, s, t;
int zl[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

struct MinCut {
	int d[MAXN];
	int pre[MAXN];
	
	bool bfs() {
		memset(d, 0, sizeof(d));
		deque<int> q;
		q.push_back(s);
		d[s] = 1;
		e.now[s] = e.hd[s];
		
		while(q.size()) {
			int x = q.front();
			q.pop_front();
			for(int i = e.hd[x]; i; i = e.nxt[i])
				if(e.w[i]) {
					int y = e.to[i];
					if(d[y])
						continue;
					
					q.push_back(y);
					e.now[y] = e.hd[y];
					d[y] = d[x] + 1;
					
					if(y == t)
						return true;
				}
		}
		return false;
	}
	int Dinic(int x, int flow) {
		if(x == t)
			return flow;
		int rest = flow, del, i;
		for(i = e.now[x]; i && rest; i = e.nxt[i]) {
			if(e.w[i]) {
				int y = e.to[i], z = e.w[i];
				if(d[y] != d[x] + 1)
					continue;
				
				del = Dinic(y, min(z, rest));
				
				if(!del)
					d[y] = 0;
				
				e.w[i] -= del;
				e.w[i ^ 1] += del;
				rest -= del;
			}
		}
		e.now[x] = i;
		return flow - rest;
	}
}MC;

int main()
{
	n = inpt(), m = inpt();
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			art[i][j] = inpt();
			ans += art[i][j];
		}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			sci[i][j] = inpt();
			ans += sci[i][j];
		}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			same_art[i][j] = inpt();
			ans += same_art[i][j];
		}
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++) {
			same_sci[i][j] = inpt();
			ans += same_sci[i][j];
		}
	
	s = GetPos(n, m) + 1, ext = t = s + 1;
	
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			int x = GetPos(i, j);
			e.Add(s, x, art[i][j]), e.Add(x, s, 0);//文科建边 
			e.Add(x, t, sci[i][j]), e.Add(t, x, 0);//理科建边 
			
			e.Add(++ext, t, same_sci[i][j]), e.Add(t, ext, 0);//同理建边 
			e.Add(x, ext, INF), e.Add(ext, x, 0);
			for(int k = 0; k < 4; k++) {
				int p = i + zl[k][0], q = j + zl[k][1];//扫描四联通 
				if(p >= 1 && p <= n && q >= 1 && q <= m) {
					int pos = GetPos(p, q);
					e.Add(pos, ext, INF), e.Add(ext, pos, 0);
				}
			}
			
			e.Add(s, ++ext, same_art[i][j]), e.Add(ext, s, 0);//同文建边 
			e.Add(ext, x, INF), e.Add(x, ext, 0);
			for(int k = 0; k < 4; k++) {
				int p = i + zl[k][0], q = j + zl[k][1];//扫描四联通 
				if(p >= 1 && p <= n && q >= 1 && q <= m) {
					int pos = GetPos(p, q);
					e.Add(ext, pos, INF), e.Add(pos, ext, 0);
				}
			}
		}
	}
	
	int del = 0;
	while(MC.bfs())
		while(del = MC.Dinic(s, INF))
			ans -= del;
	
	printf("%lld", ans);
	
	return 0;
}
2022/8/18 17:43
加载中...