「bzoj3894」文理分科 - 最小割+捆绑模型 | Bill Yang's Blog
0%

「bzoj3894」文理分科 - 最小割+捆绑模型

题目大意

    小P所在的班级要进行文理分科。他的班级可以用一个$n*m$的矩阵进行描述,每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到:
    1. 如果第$i$行第$j$列的同学选择了文科,则他将获得$art[i][j]$的满意值,如果选择理科,将得到$science[i][j]$的满意值。
    2. 如果第$i$行第$j$列的同学选择了文科,并且他相邻(两个格子相邻当且仅当它们拥有一条相同的边)的同学全部选择了文科,则他会更开心,所以会增加$same_art[i][j]$的满意值。
    3.如果第$i$行第$j$列的同学选择了理科,并且他相邻的同学全部选择了理科,则增加$same_science[i][j]$的满意值。
    小P想知道,大家应该如何选择,才能使所有人的满意值之和最大。请告诉他这个最大值。


题目分析

本题类似的一道题。
如果使用二元组建模需要新建两个点分别表示周围的点是否全选理科/文科。
在此处使用这儿介绍的第二种建模方式非常方便。


代码

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=40005;

struct Edge {
int from,to,cap,flow;
Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};

struct Dinic {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool vst[maxn];
int dist[maxn],cur[maxn];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v) {
edges.push_back(Edge(x,y,v,0));
edges.push_back(Edge(y,x,0,0));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bfs() {
memset(vst,0,sizeof(vst));
memset(dist,0,sizeof(dist));
queue<int>Q;
Q.push(t); //反向层次图
vst[t]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(!vst[Next]&&e.cap>e.flow) {
vst[Next]=1;
dist[Next]=dist[Now]+1;
Q.push(Next);
}
}
}
return vst[s];
}
int dfs(int Now,int a) {
if(Now==t||a==0)return a;
int flow=0;
for(int& i=cur[Now]; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(dist[Now]-1!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
e.flow+=nextflow;
edges[G[Now][i]^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
int flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} dinic;

const int Dirx[]= {0,-1,0,1,0},Diry[]= {0,0,1,0,-1};
int n,m,sum=0;

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

int main() {
n=Get_Int();
m=Get_Int();
dinic.init(n*m*3+2);
int Start=n*m*3+1,End=n*m*3+2;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
int x=Get_Int();
dinic.AddEdge(Start,id(i,j),x);
sum+=x;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
int x=Get_Int();
dinic.AddEdge(id(i,j),End,x);
sum+=x;
}
int cnt=id(n,m);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
int v=Get_Int();
int p=++cnt;
dinic.AddEdge(Start,p,v);
dinic.AddEdge(p,id(i,j),INT_MAX/2);
sum+=v;
for(int k=1; k<=4; k++) {
int x=i+Dirx[k],y=j+Diry[k];
if(x<1||y<1||x>n||y>m)continue;
dinic.AddEdge(p,id(x,y),INT_MAX/2);
}
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
int v=Get_Int();
int p=++cnt;
dinic.AddEdge(p,End,v);
dinic.AddEdge(id(i,j),p,INT_MAX/2);
sum+=v;
for(int k=1; k<=4; k++) {
int x=i+Dirx[k],y=j+Diry[k];
if(x<1||y<1||x>n||y>m)continue;
dinic.AddEdge(id(x,y),p,INT_MAX/2);
}
}
printf("%d\n",sum-dinic.maxflow(Start,End));
return 0;
}
姥爷们赏瓶冰阔落吧~