题解 P2941 【[USACO09FEB]环绕岛屿Surround the Islands】

· · 题解

第一个题解诶！

想要食用效果更佳戳这里

其实就是暴力；

可能是因为看不懂题才没做；

一看样例就不想做系列；并没有好好看样例；

大致看了一下分的岛屿

大概是这个样子的，然后每个点之间都有一些连线表示之间是通路，每条路都有一个权值；

其实仔细想想，既然在每个岛屿中行走不算进总花费，那么可以进行一波缩点，我是用并查集维护，直接求出每个联通块；

这样，我们就把一堆点，抽象成了一堆互不联通的块；

这时再加边劝，在每一个联通块内，任何 一个点向外的连线都可看做是这个联通块向外连得线， 这样， 我们把每一个联通块向外的边的权值最小记录下来，当做这个联通块向外的边；

所以，我们只要枚举从哪一个联通块开始出发，把这个联通块与其他联通块的边权和加起来取min再乘2就是答案；

代码奉上：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
#define regi register 

int n;

int fa[505];

inline int Find(int x)
{
    return x == fa[x] ? x : fa[x] = Find(fa[x]);
}

int dis[505][505];

int cnt;

int ans = 0x7f7f7f7f;

int pos[505];

int main()
{
    cin >> n;

    for (regi int i = 1 ; i <= n ; i ++) fa[i] = i;

    memset(dis, 0x7f, sizeof dis);

    for (regi int i = 1 ; i <= n ; i ++){
        int x, y;
        scanf("%d%d", &x, &y);
        int fx = Find(x), fy = Find(y);
        if (fx != fy) fa[fx] = fy;
    }

    for (regi int i = 1 ; i <= n ; i ++){
        if (fa[i] == i) pos[++cnt] = i;
    }

    for (regi int i = 1 ; i <= n ; i ++){
        int fi = Find(i);
        for (regi int j = 1 ; j <= n ; j ++){
            int fj = Find(j);
            int d;
            scanf("%d", &d);
            dis[fi][fj] = min(dis[fi][fj], d);            
        }
    }

    for (regi int i = 1 ; i <= cnt ; i ++){
        int sum = 0;
        for (regi int j = 1 ; j <= cnt ; j ++){
            if (i == j) continue;
            sum += dis[pos[i]][pos[j]];
        }
        ans = min(ans, sum);
    }

//    printf("dis==%d\n", dis[4][10]);

    cout << ans * 2 << endl;

    return 0;
}

zZhBr