题目大意
高一一班的座位表是个$n*m$的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。
第一行两个正整数$n,m$。
接下来是六个矩阵。
第一个矩阵为$n$行$m$列 此矩阵的第$i$行第$j$列的数字表示座位在第$i$行第$j$列的同学选择文科获得的喜悦值。
第二个矩阵为$n$行$m$列 此矩阵的第$i$行第$j$列的数字表示座位在第$i$行第$j$列的同学选择理科获得的喜悦值。
第三个矩阵为$n-1$行$m$列 此矩阵的第$i$行第$j$列的数字表示座位在第$i$行第$j$列的同学与第$i+1$行第$j$列的同学同时选择文科获得的额外喜悦值。
第四个矩阵为$n-1$行$m$列 此矩阵的第$i$行第$j$列的数字表示座位在第$i$行第$j$列的同学与第$i+1$行第$j$列的同学同时选择理科获得的额外喜悦值。
第五个矩阵为$n$行$m-1$列 此矩阵的第$i$行第$j$列的数字表示座位在第$i$行第$j$列的同学与第$i$行第$j+1$列的同学同时选择文科获得的额外喜悦值。
第六个矩阵为$n$行$m-1$列 此矩阵的第$i$行第$j$列的数字表示座位在第$i$行第$j$列的同学与第$i$行第$j+1$列的同学同时选择理科获得的额外喜悦值。
题目分析
我个人称这类二元组附加奖励值的求最值方案的题目为捆绑模型。
这类模型有两种建模方式。
对于本题，因为求最大值，我们定义割掉的权值是不选的奖励，故答案$=sum-maxflow\quad(sum$为权值总和$)$。
彭天翼论文上给出的解不定方程组代入边权值。
先考虑二元组间的附加关系，单个权值可以最后加上去。
设$S_A$是同选文科的奖励，$S_B$是同选理科的奖励，故：
如图，对于本题，二元组直接的关系的相互的，因此附加边$e$直接连成双向边即可。
列出方程组：$a+b=S_B,c+d=S_A,a+e+d=S_A+S_B,b+e+c=S_A+S_B$。
解得一组解：$e=\frac{S_A+S_B}2,a=b=\frac{S_B}2,c=d=\frac{S_A}2$。
故按照这组解建边即可，但因为权值为分数不好处理，先给权值乘$2$，求出最大流后再除以$2$即可。直接新建一个点代表奖励。
设$a[]$是选文科的奖励，$b[]$是选理科的奖励，$S_a,S_b$分别是都选文科和都选理科的奖励。
如图，与$S$相连的是选文科的奖励，与$T$相连的是选理科的奖励，我们新建结点$u$表示都选理科的奖励。
不难发现这样的模型满足要求。
代码
建模一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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
using namespace std;
typedef long long LL;
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=50005;
struct Edge {
int from,to;
LL cap,flow;
Edge(int x=0,int y=0,LL c=0,LL 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,LL 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];
}
LL dfs(int Now,LL a) {
if(Now==t||a==0)return a;
LL 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;
LL 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;
}
LL maxflow(int s,int t) {
this->s=s;
this->t=t;
LL flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,LLONG_MAX);
}
return flow;
}
} dinic;
int n,m,id[105][105];
LL sum=0,Down[maxn],Right[maxn],Art[maxn],Math[maxn];
int main() {
n=Get_Int();
m=Get_Int();
int S=n*m+1,T=n*m+2;
dinic.init(T);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
int v=Get_Int();
sum+=v;
id[i][j]=(i-1)*m+j;
Math[id[i][j]]=2*v;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
int v=Get_Int();
sum+=v;
Art[id[i][j]]=2*v;
}
for(int i=1; i<n; i++)
for(int j=1; j<=m; j++) {
int v=Get_Int();
sum+=v;
Math[id[i][j]]+=v;
Math[id[i+1][j]]+=v;
Down[id[i][j]]+=v;
}
for(int i=1; i<n; i++)
for(int j=1; j<=m; j++) {
int v=Get_Int();
sum+=v;
Art[id[i][j]]+=v;
Art[id[i+1][j]]+=v;
Down[id[i][j]]+=v;
}
for(int i=1; i<=n; i++)
for(int j=1; j<m; j++) {
int v=Get_Int();
sum+=v;
Math[id[i][j]]+=v;
Math[id[i][j+1]]+=v;
Right[id[i][j]]+=v;
}
for(int i=1; i<=n; i++)
for(int j=1; j<m; j++) {
int v=Get_Int();
sum+=v;
Art[id[i][j]]+=v;
Art[id[i][j+1]]+=v;
Right[id[i][j]]+=v;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
dinic.AddEdge(S,id[i][j],Art[id[i][j]]);
dinic.AddEdge(id[i][j],T,Math[id[i][j]]);
if(i<n) {
dinic.AddEdge(id[i][j],id[i+1][j],Down[id[i][j]]);
dinic.AddEdge(id[i+1][j],id[i][j],Down[id[i][j]]);
}
if(j<m) {
dinic.AddEdge(id[i][j],id[i][j+1],Right[id[i][j]]);
dinic.AddEdge(id[i][j+1],id[i][j],Right[id[i][j]]);
}
}
printf("%lld\n",sum-dinic.maxflow(S,T)/2);
return 0;
}
建模二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
157
158
159
160
161
162
163
164
165
166
using namespace std;
typedef long long LL;
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=50005;
struct Edge {
int from,to;
LL cap,flow;
Edge(int x=0,int y=0,LL c=0,LL 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,LL 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];
}
LL dfs(int Now,LL a) {
if(Now==t||a==0)return a;
LL 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;
LL 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;
}
LL maxflow(int s,int t) {
this->s=s;
this->t=t;
LL flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,LLONG_MAX);
}
return flow;
}
} dinic;
int n,m,cnt=0,id[105][105],tmp[105][105];
LL sum=0;
int main() {
n=Get_Int();
m=Get_Int();
int S=5*n*m+1,T=5*n*m+2;
dinic.init(T);
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
int v=Get_Int();
sum+=v;
id[i][j]=++cnt;
dinic.AddEdge(S,id[i][j],v);
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
int v=Get_Int();
sum+=v;
dinic.AddEdge(id[i][j],T,v);
}
cnt=n*m;
for(int i=1; i<n; i++)
for(int j=1; j<=m; j++) {
int v=Get_Int();
sum+=v;
cnt++;
dinic.AddEdge(S,cnt,v);
dinic.AddEdge(cnt,id[i][j],LLONG_MAX/2);
dinic.AddEdge(cnt,id[i+1][j],LLONG_MAX/2);
}
for(int i=1; i<n; i++)
for(int j=1; j<=m; j++) {
int v=Get_Int();
sum+=v;
cnt++;
dinic.AddEdge(cnt,T,v);
dinic.AddEdge(id[i][j],cnt,LLONG_MAX/2);
dinic.AddEdge(id[i+1][j],cnt,LLONG_MAX/2);
}
for(int i=1; i<=n; i++)
for(int j=1; j<m; j++) {
int v=Get_Int();
sum+=v;
cnt++;
dinic.AddEdge(S,cnt,v);
dinic.AddEdge(cnt,id[i][j],LLONG_MAX/2);
dinic.AddEdge(cnt,id[i][j+1],LLONG_MAX/2);
}
for(int i=1; i<=n; i++)
for(int j=1; j<m; j++) {
int v=Get_Int();
sum+=v;
cnt++;
dinic.AddEdge(cnt,T,v);
dinic.AddEdge(id[i][j],cnt,LLONG_MAX/2);
dinic.AddEdge(id[i][j+1],cnt,LLONG_MAX/2);
}
printf("%lld\n",sum-dinic.maxflow(S,T));
return 0;
}
