题面

分析

这道题类似于BZOJ 3774 最优选择,然后这里有一篇博客写的很好…

应该看懂了吧…不懂的画画图,分分情况会发现…这连边…好妙啊

CODE

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

template<typename T>inline void read(T &num) {

    char ch; while((ch=getchar())<'0'||ch>'9');

    for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());

}

const int inf = 1e9;

const int MAXN = 30005;

const int MAXM = 2000005;

const int dx[] = { 1, -1, 0, 0, 0 };

const int dy[] = { 0, 0, -1, 1, 0 };

int n, m, fir[MAXN], S, T, cnt;

struct edge { int to, nxt, c; }e[MAXM];

inline void add(int u, int v, int cc) {

	e[cnt] = (edge){ v, fir[u], cc }; fir[u] = cnt++;

	e[cnt] = (edge){ u, fir[v], 0 }; fir[v] = cnt++;

}

int dis[MAXN], vis[MAXN], info[MAXN], cur, q[MAXN];

inline bool bfs() {

	int head = 0, tail = 0;

	vis[S] = ++cur; q[tail++] = S;

	while(head < tail) {

		int u = q[head++];

		for(int i = fir[u]; ~i; i = e[i].nxt)

			if(e[i].c && vis[e[i].to] != cur)

				vis[e[i].to] = cur, dis[e[i].to] = dis[u] + 1, q[tail++] = e[i].to;

	}

	if(vis[T] == cur) memcpy(info, fir, (T+1)<<2);

	return vis[T] == cur;

}

int dfs(int u, int Max) {

	if(u == T || !Max) return Max;

	int flow=0, delta;

	for(int &i = info[u]; ~i; i = e[i].nxt)

		if(e[i].c && dis[e[i].to] == dis[u] + 1 && (delta=dfs(e[i].to, min(e[i].c, Max-flow)))) {

			e[i].c -= delta, e[i^1].c += delta, flow += delta;

			if(flow == Max) return flow;

		}

	return flow;

}

inline int dinic() {

	int flow=0, x;

	while(bfs()) {

		while((x=dfs(S, inf))) flow+=x;

	}

	return flow;

}

int art[105][105], sci[105][105], same_a[105][105], same_s[105][105];

inline int enc(int i, int j, int k) { return (i-1)*m + j + k*n*m; }

int main () {

	memset(fir, -1, sizeof fir);

	read(n), read(m); S = 0; T = n*m*3+1; int sum = 0;

	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) read(art[i][j]);

	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) read(sci[i][j]);

	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) read(same_a[i][j]);

	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) read(same_s[i][j]);

	for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) {

		add(S, enc(i, j, 0), art[i][j]); sum += art[i][j];

		add(enc(i, j, 0), T, sci[i][j]); sum += sci[i][j];

		add(S, enc(i, j, 1), same_a[i][j]); sum += same_a[i][j];

		add(enc(i, j, 2), T, same_s[i][j]); sum += same_s[i][j];

		for(int l = 0, x, y; l < 5; ++l)

			if((x=i+dx[l]) >= 1 && x <= n && (y=j+dy[l]) >= 1 && y <= m) {

				add(enc(i, j, 1), enc(x, y, 0), inf);

				add(enc(x, y, 0), enc(i, j, 2), inf);

			}

	}

	printf("%d\n", sum-dinic());

}

巴特西

BZOJ 3894 / Luogu P4313 文理分科 (拆点最小割)

题面

分析

CODE

最新文章

热门文章