【BZOJ 3894】文理分科

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3894
神犇题解：http://blog.csdn.net/popoqqq/article/details/43968017

解题报告

如果“同选文或同选理”这种有加成的关系只局限于两个人之间
那大家肯定都会，建图方法如下：

但这题有加成的关系不限于两点之间，而是五点之间
似乎没法做了，但让我们来考虑最小割的意义：

最后将原图划分为两个集合：S集 & T集

于是我们不妨设最后在S集的点选文，T集的点选理
这样的话，考虑选文的点需要花费多少费用：

1. 选理的费用
2. 同选理的费用

第一个很好解决，向T直接边就好
第二个因为涉及5个点，于是只能新建 关键点 再从 关键点 连向汇点
酱紫的话，似乎就非常好理解了？

现在再重新考虑之前提到的仅限于两点间的加成的情况
似乎也可以这样来建图，似乎只是边数和点数多了一点：

再仔细想一想的话，似乎只是把可以合并的边给合并掉了？

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 30000+9;
const int M = 300000+9; 
const int INF = 1e9;

int n,m,S,T,head[N],to[M],nxt[M],flow[M];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1},vout;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v, int f = INF) {
	static int T = 1;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; flow[T] = f;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; flow[T] = 0;
}

inline int id(int x, int y, int t) {
	return n * m * (t - 1) + (y - 1) * n + x;
}

class MaxFlow{
	int cur[N],dis[N];
	queue<int> que;
	public:
		inline int solve() {
			int ret = 0;
			while (BFS()) {
				memcpy(cur, head, sizeof(head));
				ret += DFS(S, INF);
			}	
			return ret;
		}
	private:
		inline bool BFS() {
			memset(dis,60,sizeof(dis));
			que.push(S); dis[S] = 0;
			
			while (!que.empty()) {
				int w = que.front(); que.pop();
				for (int i=head[w];i;i=nxt[i]) {
					if (dis[to[i]] > INF && flow[i]) {
						dis[to[i]] = dis[w] + 1;
						que.push(to[i]);
					}
				}
			}
			return dis[T] < INF;
		}
		int DFS(int w, int f) {
			if (w == T) return f;
			else {
				int ret = 0;
				for (int tmp,&i=cur[w];i;i=nxt[i]) {
					if (dis[to[i]] == dis[w] + 1 && flow[i]) {
						tmp = DFS(to[i], min(f, flow[i])); 
						flow[i] -= tmp; flow[i^1] += tmp;
						f -= tmp; ret += tmp;
						if (!f) break;
					}
				}
				return ret;
			}
		}
}Dinic;

int main() {
	m = read(); n = read();
	S = 0; T = N - 1;
	for (int j=1,tmp;j<=m;j++) 
		for (int i=1;i<=n;i++)
			vout += (tmp = read()), 
			Add_Edge(id(i,j,1), T, tmp);
	for (int j=1,tmp;j<=m;j++) 
		for (int i=1;i<=n;i++)
			vout += (tmp = read()), 
			Add_Edge(S, id(i,j,1), tmp);
	for (int j=1,tmp;j<=m;j++)
		for (int i=1;i<=n;i++)
			vout += (tmp = read()), 
			Add_Edge(id(i,j,3), T, tmp);
	for (int j=1,tmp;j<=m;j++)
		for (int i=1;i<=n;i++)
			vout += (tmp = read()), 
			Add_Edge(S, id(i,j,2), tmp);
	for (int j=1,w=0;j<=m;j++) {
		for (int i=1;i<=n;i++) {
			Add_Edge(id(i,j,1), id(i,j,1));
			Add_Edge(id(i,j,2), id(i,j,1));
			Add_Edge(id(i,j,1), id(i,j,3));
			for (int k=0,x,y;k<4;k++) {
				x = i + dx[k];
				y = j + dy[k];
				if (1 <= x && x <= n && 1 <= y && y <= m) {
					Add_Edge(id(i,j,2), id(x,y,1));
					Add_Edge(id(x,y,1), id(i,j,3));
				}
			}
		}
	}
	printf("%d\n",vout-Dinic.solve());
	return 0;
}