P2771 [USACO16JAN]Build Gates S 题解

· · 题解

题意

FJ 从 (0,0) 开始在一个平面上走动（无限制），会在走过的路径上留下栅栏， 形成一些封闭的空间。而现在要求把尽量少的一部分栅栏换成门（也可以看做删除这段栅栏），使得整个平面连通。

思路

方法一

答案很明显，因为对于每一个环至少需要一次删边才能解开这个环，那么删边的最小次数即是环的数量。但是对于一条边可能包含在多个环中，一次就会满足多个环，每个环都算就会出现错误，所以我们把图中那些不包含其他环的环的数量求出来就可以了，而之所以求这样的环，是因为只有这种环才能保证环内有且仅有一个封闭空间，那么对于每一个这种环进行一次删边就符合题意了。

例如样例：

（紫色的是起点）因为有两个这样（黄色区域和蓝色区域）的环，所以 ans=2。

再举个例子：

在这个图中就存在 3 个符合上文要求的环（黄、蓝、绿），虽然黄绿部分也能组成环，但这个环内存在两个封闭空间，所以不能算，故 ans=3。

到这里就不难发现，一个点如果到过，那么从另一个没走过的方向再次到这个点会形成一个新的符合要求的环, 因为这样就表明出现一条新的路径连接到了这个点，也必然会多且仅多出一个封闭空间，也就使答案加一。到这里为止，一个大体的算法就出来了，我们首先使 FJ 一边移动一边把路径存下来，我们设 FJ 现在所处的点为 k，到点 k 之前的点为 k-1，如果 k 不是第一次到，并且 FJ 从点 k-1 到点 k 之前不存在这条路径，则 ans+1。

完整代码如下：

#include<bits/stdc++.h>
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
const char s[] = {'N', 'S', 'W', 'E'};
const int N = 2e3 + 10, M = 2e3 + 10;
using namespace std;
int n, x = 1000, y = 1000, xt = 1000, yt =1000, num, bol[N][M], f[N][M], a[N][M], ans;
/* 
n表示FJ行走的步数
(x, y)表示上文中的 k
(xt, yt)表示上文中的 k - 1 
num表示FJ所到达的不同的点的个数 
bol[i][j]表示坐标为(i, j)的点是否到过
f[i][j]表示编号i和编号j的点是否存在路径
a[i][j]表示坐标为(i, j)的点的编号
ans表示答案 
*/ 
int main() {
    scanf("%d\n", &n); num = 1, bol[1000][1000] = 1, a[1000][1000] = 1;
    //因为有负坐标，所以起点坐标设为(1000, 1000);同时给起点编号为 1 
    for(int i = 1; i <= n; ++i) {
        char c; scanf("%c", &c);
        for(int j = 0; j < 4; ++j) {
            if(c == s[j]) {x += dx[j], y += dy[j]; break;}
        } //按读入移动并求出坐标(x, y) 
        if(!bol[x][y]) a[x][y] = ++num;
        //如果点(x, y)第一次到，给(x, y)编号为已有点个数 + 1 
        int last = a[xt][yt], now = a[x][y];
        //last表示坐标(xt, yt)的编号，now表示坐标(x, y)的编号 
        if(!f[last][now] && bol[x][y]) ++ans;
        //如果点 k 不是第一次到，并且FJ从点 k - 1 到点 k 之前不存在这条路径，则 ans + 1
        f[last][now] = f[now][last] = 1;
        //标记点 k - 1 到点 k 的路径存在 
        xt = x, yt = y; bol[x][y] = 1;
        //更新点 k - 1 为 k，并标记点 k 到过； 
    }
    printf("%d\n", ans);
    //输出答案 
    return 0;
}

方法二

先分析一下 : 因为这个图是 FJ 所走的路径，所以一定是联通的。而如果图中出现了环，也就一定代表出现了封闭空间，那么也只有当图中没有环之后才会满足题意，题目要求删边最少等价于留边最多，当一个图不存在环时，树的边是最多的，再多就一定会出现环，所以保证图是一棵树是一定是最优解，如果图中点数为 n 边数为 p，则 ans=p-(n-1)，其中 n-1 表示树的边数。

例如样例：

样例点数为 13 边数为 14，故 ans=14-(13-1)=2。

还是上面的例子：

点数为 18 边数为 20，故 ans=20-(18-1)=3。

完整代码如下：

#include<bits/stdc++.h>
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
const char s[] = {'N', 'S', 'W', 'E'};
const int N = 2e3 + 10, M = 2e3 + 10;
using namespace std;
int n, x = 1000, y = 1000, xt = 1000, yt =1000, num, bol[N][M], f[N][M], a[N][M], num1;
/* 
n表示FJ行走的步数
(x, y)表示上文中的 k
(xt, yt)表示上文中的 k - 1 
num表示FJ所到达的不同的点的个数 
bol[i][j]表示坐标为(i, j)的点是否到过
f[i][j]表示编号i和编号j的点是否存在路径
a[i][j]表示坐标为(i, j)的点的编号
num1表示FJ移动所留下的边数 
*/ 
int main() {
    scanf("%d\n", &n); num = 1, bol[1000][1000] = 1, a[1000][1000] = 1;
    //因为有负坐标，所以起点坐标设为(1000, 1000);同时给起点编号为 1 
    for(int i = 1; i <= n; ++i) {
        char c; scanf("%c", &c);
        for(int i = 0; i < 4; ++i) {
            if(c == s[i]) {x += dx[i], y += dy[i]; break;}
        } //按读入移动并求出坐标(x, y) 
        if(!bol[x][y]) a[x][y] = ++num, bol[x][y] = 1;
        //如果点(x, y)第一次到，给(x, y)编号为已有点个数 + 1，并标记为到过 
        int last = a[xt][yt], now = a[x][y];
        //last表示坐标(xt, yt)的编号，now表示坐标(x, y)的编号 
        if(!f[last][now]) {
            f[last][now] = f[now][last] = 1;
            ++num1;
        }
        //如果这条边是新建的，则边数 + 1 
        xt = x, yt = y;
        //更新点 k - 1 为 k
    }
    printf("%d\n", num1 - num + 1);
    //有没有可能减出负数呢？答案是不会，因为FJ所走的路径一定联通，所以整个图至少也会是一棵树，答案最小也就为num - 1（树的边数） 
    return 0;
}