题外话

我们模拟赛考了这题。

模拟赛大概还剩一个半小时的时候,我想出了这题,并且说

“要是我这没A掉,我就不交卷了”

于是我就没有A掉。

其实赛后半个小时左右就调出来了(我才不会告诉你我比赛的时候那个建模是有锅的呢)

大思路

首先考试的时候去做另外两题

我另外两题暴力刚敲完,旁边的$Isonan$爷大吼一声

A了!

于是我一惊,$Isonan$爷固然巨,但是考试才过了1个小时,这题似乎不难,我开始考虑正解。

我看到这$n = 50$的数据规模,我意识到这题正解估计就是网络流之类的解法

看到这个神奇的$L$字形,我们就可以往奇偶分层方面想。

鬼畜建模

首先,我们马上可以想到把$x + y$为奇数的有权的点给拎出来,称为a类点

然后把剩下来无点权的点分类

如果它在偶数行,称为b类点

否则称为c类点

那么一个3*3的矩阵分类之后长这样↓

1
2
3
4
5
6
7
+-+-+-+
|c|a|c|
+-+-+-+
|a|b|a|
+-+-+-+
|c|a|c|
+-+-+-+

然后显然,贪心地想,一个L字形必须得放在有点权的A类点上

那么感性理解一下,一个L字形肯定是由一个a一个b一个c组成的

然后继续感性理解,我们可以弄出来一个类似带权三分图匹配(大雾)之类的东西

具体是这样的

  • 源点向源点2 连边 流量$m$费用0(最多放$m$个石头)

  • 源点2 向 $b$连边,流量$1$ 费用$0$

  • 将$a$拆点

  • $b$ 向 $a$入点连边,流量$1$ 费用$0$

  • $a$ 入点向 $a$ 出点连边,流量$1​$,费用为该点的点权

  • $a$ 出点向 $c$ 连边,流量$1$,费用$0$

  • $c$ 向汇点连边,流量$1$,费用$0$

  • 最后跑最大费用最大流即可。

由于我以前有个假的解法,导致我的$b$和$c$类点也拆了点,所以可以不用在意,意思对就行。

需要注意的一个坑

每次增广之后都应该重新统计一遍答案,因为$m$的流量不一定要流满。

代码实现

具体的还是上代码吧。

实现的比较丑,轻喷。

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
#include<bits/stdc++.h>

#define INF 2147483647
#define ll long long
#define get(i, j) ((i - 1) * n + j)

int inp(){
char c = getchar();
int neg = 1;
while(c < '0' || c > '9'){
if(c == '-')
neg = -1;
c = getchar();
}
int sum = 0;
while(c >= '0' && c <= '9'){
sum = ((sum << 3) + (sum << 1)) + c - '0';
c = getchar();
}
return neg * sum;
}

const int opt[10][4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int head[200010];
int nxt[500010];
int end[500010];
int value[500010];
int cost[500010];
int dis[200010];
int prev1[200010];
int prev2[200010];
bool inq[200010];
int q[1000010];
bool dag[100][100];
int w[100][100];
int Cou = -1;

void link(int a, int b, int v, int c){
// printf("linked %d and %d\n", a, b);
nxt[++Cou] = head[a];
head[a] = Cou;
end[Cou] = b;
value[Cou] = v;
cost[Cou] = c;

nxt[++Cou] = head[b];
head[b] = Cou;
end[Cou] = a;
value[Cou] = 0;
cost[Cou] = -c;
}

int main(){
memset(head, -1, sizeof(head));
int n = inp();
int m = inp();
int k = inp();
int sum = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
w[i][j] = inp();
sum += w[i][j];
}
for(int i = 1; i <= k; i++){
int x = inp();
int y = inp();
dag[x][y] = true;
}
int s = 0;
link(s, 200001, m, 0);
int e = 200000;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
if((i + j) & 1){
link(get(i, j), get(i, j) + (n * n), 1, -w[i][j]);
if(i & 1){
if(j > 1)
link(get(i, j) + (n * n), get(i, j - 1), 1, 0);
if(j < n)
link(get(i, j) + (n * n), get(i, j + 1), 1, 0);
} else {
if(i > 1)
link(get(i, j) + (n * n), get(i - 1, j), 1, 0);
if(i < n)
link(get(i, j) + (n * n), get(i + 1, j), 1, 0);
}
} else {
if(dag[i][j])
continue;
link(get(i, j), get(i, j) + (n * n), 1, 0);
if(i & 1){
link(get(i, j) + (n * n), e, 1, 0);
} else {
link(200001, get(i, j), 1, 0);
for(int u = 0; u < 4; u++){
int tx = i + opt[u][0];
int ty = j + opt[u][1];
if(tx < 1 || tx > n || ty < 1 || ty > n)
continue;
link(get(i, j) + (n * n), get(tx, ty), 1, 0);
}
}
}
}

int flow = 0;
int ans = 0;
int f = INF;
int ret = 0;
while(f > 0){
memset(inq, false, sizeof(inq));
memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
q[1] = s;
int qf = 1;
int qe = 1;
int sum = 0;
while(qf <= qe){
int u = q[qf++];
inq[u] = false;
sum -= dis[u];
for(int x = head[u]; x != -1; x = nxt[x]){
if(value[x] > 0 && dis[end[x]] > dis[u] + cost[x]){
if(inq[end[x]])
sum -= dis[end[x]];
dis[end[x]] = dis[u] + cost[x];
prev1[end[x]] = u;
prev2[end[x]] = x;
sum += dis[end[x]];
if(!inq[end[x]]){
q[++qe] = end[x];
inq[end[x]] = true;
}
}
}
}

// for(int i = 1; i <= 20; i++)
// printf("%d ", dis[i]);
// putchar('\n');
if(dis[e] == dis[200002])
break;
int delta = f;
for(int i = e; i != s; i = prev1[i]){
// printf("%d<-(%d)--", i % (n * n), value[prev2[i]]);
delta = std::min(delta, value[prev2[i]]);
}
// putchar('\n');
f -= delta;
flow += delta;
ans += delta * dis[e];
for(int i = e; i != s; i = prev1[i]){
value[prev2[i]] -= delta;
value[prev2[i] ^ 1] += delta;
}
ret = std::min(ret, ans);
}
printf("%d", sum + ret);
}

 评论