CF1898F 题解
huangrenheluogu
·
·
题解
我的翻译：
定义在边缘的点为出口。
定义一个点有三种类型：
- `1 型点`：恰好可以到 $0$ 个出口。
- `2 型点`：恰好可以到 $1$ 个出口。
- `3 型点`：可以到 $2$ 个或 $2$ 个以上的出口。
Vova 在一个点，Misha 可以将一些空点变成有障碍物的点（Vova 所在的点除外），但是 Misha 不能改变 Vova 所在点的类型。
求 Misha 可以增加障碍物数量的最大值。
$t\le10^4,1\le n,m\le1000,\sum n\times m\le10^6$。
------------------------------
先跑图，知道 Vova 所在的点是哪种类型的点。
分类讨论：
- `1 型点`
那么直接输出 $tot-1$，$tot$ 为总共空的点。
- `2 型点`
输出 $tot-minn$，其中 $minn$ 是中心点到周围至少经过的点。
- `3 型点`
考虑保留两条路径，我们可以在第一次跑图的过程中得出第 $(x,y)$ 这个点距离不同的出口最短距离、次短距离。
然后从 Vova 所在的点出发，到一个点就判断，总路程就是 $(x,y)$ 到出口的最小距离加次小距离，和 Vova 所在点到 $(x,y)$ 的距离。
注意处理一下点数和边数的差距即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1005, inf = 1e9;
int n, m, dis[N][N][2], T, cnt, tot, X, Y, t, h, x, y, nx, ny, dist, Dis[N][N], a[N][N], xx, yy;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
char c;
struct nod{
int x, y, frox, froy, dis;//frox, froy 记录点的来源
}q[N * N * 2], id[N][N];
inline bool check(int x, int y){
return x < 1 || x > n || y < 1 || y > m || a[x][y];
}
inline void work(){
scanf("%d%d", &n, &m);
h = t = tot = cnt = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
c = getchar();
while(c != '#' && c != '.' && c != 'V') c = getchar();
if(c == '#') a[i][j] = 1;
else a[i][j] = 0;
if(c == 'V') X = i, Y = j;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
dis[i][j][0] = dis[i][j][1] = inf, id[i][j] = (nod){-1, -1, 0, 0};
if(a[i][j] == 0){
tot++;
if(i == 1 || j == 1 || i == n || j == m) q[++t] = (nod){i, j, i, j, 0}, dis[i][j][0] = 0, id[i][j] = (nod){i, j, 0, 0, 0};//第一遍，我用边数记录
}
}
}
while(h < t){
h++;
x = q[h].x, y = q[h].y, dist;
xx = q[h].frox, yy = q[h].froy;
dist = q[h].dis;
for(int i = 0; i < 4; i++){
nx = x + dx[i];
ny = y + dy[i];
if(check(nx, ny)) continue ;
if(dis[nx][ny][0] > dist + 1){
dis[nx][ny][0] = dist + 1;
id[nx][ny] = (nod){xx, yy};
q[++t] = (nod){nx, ny, xx, yy, dist + 1};
}
else{
if(dis[nx][ny][1] > dist + 1 && (xx != id[nx][ny].x || yy != id[nx][ny].y)){
dis[nx][ny][1] = dist + 1;
id[nx][ny] = (nod){xx, yy, 0, 0, 0};
q[++t] = (nod){nx, ny, xx, yy, dist + 1};
}
}
}
}
if(dis[X][Y][0] == inf){//1型点
printf("%d\n", tot - 1);
return ;
}
if(dis[X][Y][1] == inf){//2型点
printf("%d\n", tot - dis[X][Y][0] - 1);
return ;
}
h = t = 0;
q[++t] = (nod){X, Y};
cnt = tot;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
Dis[i][j] = inf;
}
}
Dis[X][Y] = 1;//第二遍，我用经过的点数记录，这样加起来刚好
while(h < t){
h++;
x = q[h].x, y = q[h].y;
dist = Dis[x][y];
cnt = min(cnt, dist + dis[x][y][0] + dis[x][y][1]);
for(int i = 0; i < 4; i++){
nx = x + dx[i];
ny = y + dy[i];
if(check(nx, ny)) continue ;
if(Dis[nx][ny] > dist + 1){
Dis[nx][ny] = dist + 1;
q[++t] = (nod){nx, ny, 0, 0, dist + 1};
}
}
}
printf("%d\n", tot - cnt);
return ;
}
int main(){
scanf("%d", &T);
while(T--){
work();
}
return 0;
}
```
洛谷上 UKE 了， 放一张 CF 的评测图吧。
upd：洛谷上过了。