luoguP4313 文理分科

luoguP4313 文理分科

复习完之后做了道典型题目。

这道题条件有点多

我们逐个分析

如果没有(sameart)或者(samescience)的限制,就是一个裸的最大权闭合子图的问题了

但是再考虑有的话（其实还是一个最大权闭合子图）

很明显我们还是可以按照套路分成两个集合.

然后先按照权值分别划分(S),(T)集合

然后再向他要求的学生连一条(infty)

放一张奇丑无比的图

感性理解一下就好了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cctype>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 2e5 + 3;
const int M = 2e6 + 3;
const int INF = 2e9; 
int cur[N],head[N],high[N];
struct edge{
	int to;
	int nxt;
	int flow;	
}e[M];
int n,m,tot = 1,s,t;
int ans = 0;
int dx[5] = {0,1,-1,0,0},dy[5] = {0,0,0,1,-1};
inline void add(int x,int y,int z){
	e[++tot].to = y;
	e[tot].flow = z;
	e[tot].nxt = head[x];
	head[x] = tot;
	if(z < INF) ans += z;	
}
inline int read(){
	int v = 0,c = 1;char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') c = -1;
		ch = getchar();	
	}
	while(isdigit(ch)){
		v = v * 10 + ch - 48;
		ch = getchar();	
	}
	return v * c;
}
inline bool bfs(){
	queue <int> q;
	for(int i = 0;i <= t;++i) high[i] = 0;
	q.push(s);high[s] = 1;
	while(!q.empty()){
		int k = q.front();q.pop();
		for(int i = head[k];i;i = e[i].nxt){
			int y = e[i].to;
			if(!high[y] && e[i].flow > 0)
			q.push(y),high[y] = high[k] + 1;	
		}
	}
	return high[t] != 0;
}
inline int dfs(int x,int dis){
	if(x == t) return dis;
	for(int &i = cur[x];i;i = e[i].nxt){
		int y = e[i].to;
		if(high[y] == high[x] + 1 && e[i].flow > 0){
			int flow = dfs(y,min(dis,e[i].flow));
			if(flow > 0){
				e[i].flow -= flow;
				e[i ^ 1].flow += flow;
				return flow;	
			}
		}
	}
	return 0;
}
inline int dinic(){
	int res = 0;
	while(bfs()){
		for(int i = 0;i <= t;++i) cur[i] = head[i];
		while(int now = dfs(s,INF)) res += now;
	}
	return res;
}
int main(){
	n = read(),m = read();
	s = 3 * n * m + 1,t = s + 1;
	for(int i = 0;i < n;++i)
		for(int j = 0;j < m;++j){
			int x = read();
			add(s,i * m + j,x);
			add(i * m + j,s,0);	
		}
	for(int i = 0;i < n;++i)
		for(int j = 0;j < m;++j){
			int x = read();
			add(i * m + j,t,x);
			add(t,i * m + j,0);	
		}
	for(int i = 0;i < n;++i)
		for(int j = 0;j < m;++j){
			int x = i * m + j + n * m,y = x + n * m;
			for(int k = 0;k < 5;++k){
				int xx = i + dx[k],yy = j + dy[k];
				if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
				add(x,xx * m + yy,INF);add(xx * m + yy,x,0);
				add(xx * m + yy,y,INF);add(y,xx * m + yy,0);
			//	add(x,xx * n + yy,0);add(xx * n + yy,x,INF);
			//	add(xx * n + yy,y,0);add(y,xx * n + yy,INF);
			}
		}
	for(int i = 0;i < n;++i)
		for(int j = 0;j < m;++j){
			int x = read();
			add(s,i * m + j + n * m,x);
			add(i * m + j + n * m,s,0);	
		}
	for(int i = 0;i < n;++i)
		for(int j = 0;j < m;++j){
			int x = read();
			add(i * m + j + 2 * n * m,t,x);
			add(t,i * m + j + 2 * n * m,0);	
		}
//	cout << ans << endl;
	ans -= dinic();
	printf("%d
",ans);
	return 0;	
}