bzoj 3894 文理分科

Posted on | Views:

最小割.

最小割经典模型,一个集合中的元素全选时会产生一个额外收益.

先把所有的收益和额外收益都加入答案,然后对于每个人 $x$ ,连边 $S\to x,x\to T$ ,权值分别为选文,选理的收益.

对于每个人,再新建一个点 $y$ ,将自己以及与它四连通的点向 $y$ 连边,权值为 $\infty$ .

将 $y$ 向 $T$ 连边,权值为这些人都选理的收益,表示这些人中只要有一个人选了文,都选理的收益就没有了.

都选理的处理方法同理.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int inf=1e9;
const int MAXN=1e3+10;
int art[MAXN][MAXN],sci[MAXN][MAXN],same_art[MAXN][MAXN],same_sci[MAXN][MAXN],id[MAXN][MAXN];
int n,m,tot=0,ans=0;
void Read(int a[MAXN][MAXN])
{
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			ans+=(a[i][j]=read());
}
const int N=3e4+10,M=2e6+10;
int head[N],ecnt=1;
struct Edge
{
	int nx,to,flow;
	Edge(int nx=0,int to=0,int flow=0):nx(nx),to(to),flow(flow) {}
}E[M];
void addedge(int u,int v,int w)
{
	E[++ecnt]=Edge(head[u],v,w);
	head[u]=ecnt;
}
void ins(int u,int v,int w)
{
	addedge(u,v,w);
	addedge(v,u,0);
}
int cur[N],dep[N];
queue<int> q;
bool bfs(int S,int T)
{
	for(int i=1;i<=tot;++i)
		dep[i]=-1,cur[i]=head[i];
	dep[S]=0;
	q.push(S);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=E[i].nx)
		{
			int v=E[i].to;
			if(E[i].flow>0 && dep[v]==-1)
			{
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	return dep[T]!=-1;
}
int dfs(int u,int T,int limit)
{
	if(u==T || !limit)
		return limit;
	int f,flow=0;
	for(int &i=cur[u];i;i=E[i].nx)
	{
		int v=E[i].to;
		if(E[i].flow>0 && dep[v]==dep[u]+1 && (f=dfs(E[i].to,T,min(limit,E[i].flow))))
		{
			E[i].flow-=f;
			E[i^1].flow+=f;
			flow+=f;
			limit-=f;
		}
		if(!limit)
			break;
	}
	return flow;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			id[i][j]=++tot;
	Read(art);
	Read(sci);
	Read(same_art);
	Read(same_sci);
	int S=++tot,T=++tot;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			int x=id[i][j],y=++tot;
			ins(S,x,art[i][j]);
			ins(x,T,sci[i][j]);
			ins(y,T,same_sci[i][j]);			
			ins(x,y,inf);
			if(i>1)
				ins(id[i-1][j],y,inf);
			if(i<n)
				ins(id[i+1][j],y,inf);
			if(j>1)
				ins(id[i][j-1],y,inf);
			if(j<m)
				ins(id[i][j+1],y,inf);
			y=++tot;
			ins(S,y,same_art[i][j]);
			ins(y,x,inf);
			if(i>1)
				ins(y,id[i-1][j],inf);
			if(i<n)
				ins(y,id[i+1][j],inf);
			if(j>1)
				ins(y,id[i][j-1],inf);
			if(j<m)
				ins(y,id[i][j+1],inf);
		}
	while(bfs(S,T))
		ans-=dfs(S,T,inf);
	cout<<ans<<endl;
	return 0;
}