P2941 [USACO09FEB]Surround the Islands S

P2941 [USACO09FEB]Surround the Islands S

并查集水题，按照题意维护每个岛作为一个集合即可。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 510, inf = 5e5;
int n, p[N], d[N][N];
int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        p[i] = i;
    for (int i = 1, a, b; i <= n; i++)
    {
        scanf("%d%d", &a, &b);
        a = find(a), b = find(b);
        p[a] = b;
    }
    for (int i = 1; i <= n; i++)
        p[i] = find(i);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = i == j ? 0 : inf;
    for (int i = 1, a; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            scanf("%d", &a);
            d[p[i]][p[j]] = d[p[j]][p[i]] = min(d[p[i]][p[j]], a);
        }
    int res = inf;
    for (int i = 1; i <= n; i++)
        if (i == p[i])
        {
            int s = 0;
            for (int j = 1; j <= n; j++)
                if (j == p[j])
                    s += d[i][j];
            res = min(res, s);
        }
    printf("%d", res << 1);
    return 0;
}