小希的迷宫

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

int p[N]; // p[i]存的是i节点的父(根)节点
int a, b;
int flag;
int st[N];

void init() {  //并查集的初始化
    for (int i = 1; i <= N; i ++ ) {

        p[i] = i;
        st[i] = 0;
    }
}

int find(int x) { // 返回x所在集合的根节点(路径压缩)
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

void merge(int a, int b) { // 合并a、b两个集合
    int fa = find(a), fb = find(b);
    p[fa] = fb;
}

int main() {
    while (cin >> a >> b) {
        if (a == -1 && b == -1)
            break;

        init();
        flag = 0;

        while (1) {
            if (a == 0 && b == 0)
                break;

            if (find(a) == find(b)) // 查询两个元素是否位于同一个集合当中
                flag = 1;
            merge(a, b);
            st[a] = st[b] = 1;
            cin >> a >> b;
        }

        if (flag == 1) {
            puts("No");
            continue;
        }

        int sum = 0; // 统计一下构建迷宫的个数

        for (int i = 1; i <= N; i ++ )

            if (st[i] && p[i] == i)
                sum ++ ;

        if (sum > 1)
            puts("No");
        else
            puts("Yes");
    }

    return 0;
}

More is better

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e7 + 10;

int p[N]; // p[i]存的是i节点的父(根)节点
int a, b;
int size[N]; // size[i]表明i节点的集合大小(i是根节点)
int n;

void init() {  //并查集的初始化
    for (int i = 1; i <= N; i ++ ) {

        p[i] = i;
        size[i] = 1;
    }
}

int find(int x) { // 返回x所在集合的根节点(路径压缩)
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

void merge(int a, int b) { // 合并a、b两个集合
    int fa = find(a), fb = find(b);

    if (fa != fb) {
        p[fa] = fb;
        size[fb] += size[fa];
    }
}

int main() {
    while (~scanf("%d", &n)) {
        if (n == 0) {
            puts("1");
            continue;
        }

        init();
        int m = 0;

        while (n -- ) {
            scanf("%d%d", &a, &b);

            if (m < a)
                m = a;

            if (m < b)
                m = b;
            merge(a, b);
        }

        int MAX = 1;

        for (int i = 1; i <= m; i ++ )

            if (p[i] == i)
                MAX = max(MAX, size[i]);

        printf("%d\n", MAX);
    }

    return 0;
}

继续畅通工程

并查集

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 5010;

int p[110]; // p[i]存的是i节点的父(根)节点
int n;

struct node {
    int a, b;
    int w;
    int f;
} load[N];

bool cmp(node A, node B) {
    if (A.f != B.f)
        return A.f > B.f;
    return A.w < B.w;
}

void init(int n) {  //并查集的初始化
    for (int i = 1; i <= n; i ++ ) {

        p[i] = i;
    }
}

int find(int x) { // 返回x所在集合的根节点(路径压缩)
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

int main() {
    while (scanf("%d", &n)) {
        if (n == 0)
            break;
        init(n);

        for (int i = 1; i <= (n - 1) * n / 2; i ++ )

            scanf("%d%d%d%d", &load[i].a, &load[i].b, &load[i].w, &load[i].f);
        sort(load + 1, load + 1 + (n - 1) * n / 2, cmp);
        int ans = 0;

        for (int i = 1; i <= (n - 1) * n / 2; i ++ ) {

            int fa = find(load[i].a), fb = find(load[i].b);
            if (fa != fb) {
                p[fa] = fb;

                if (!load[i].f)
                    ans += load[i].w;
            }
        }

        printf("%d\n", ans);
    }

    return 0;
}

prim

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m, k;
int g[N][N]; // g[i][j]表示一条从i指向j的线
int dist[N]; // dist[i]表示i到集合的最短距离
bool st[N];  // st[i] = true表示i在集合中

int prim() {
    memset(dist, 0x3f, sizeof dist);
    int res = 0;

    for (int i = 0; i < n; i ++ ) {

        int t = -1;

        for (int j = 1; j <= n; j ++ )

            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        if (i && dist[t] == INF)
            return INF;

        if (i)
            res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ )

            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main() {
    while (~scanf("%d", &n)) {
        if (n == 0) break;
        memset(g, 0x3f, sizeof g);
        memset(st, false, sizeof st);

        for (int i = 1; i <= (n - 1) * n / 2; i ++ ) {

            int a, b, c, f;
            scanf("%d%d%d%d", &a, &b, &c, &f);

            if (!f)
                g[a][b] = g[b][a] = min(g[a][b], c);
            else
                g[a][b] = g[b][a] = 0;
        }

        printf("%d\n", prim());
    }

    return 0;
}

Connect the Cities

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m, k;
int g[N][N]; // g[i][j]表示一条从i指向j的线
int dist[N]; // dist[i]表示i到集合的最短距离
int city[N];
bool st[N];  // st[i] = true表示i在集合中

int prim() {
    memset(dist, 0x3f, sizeof dist);
    int res = 0;

    for (int i = 0; i < n; i ++ ) {

        int t = -1;

        for (int j = 1; j <= n; j ++ )

            if (!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;

        if (i && dist[t] == INF)
            return INF;

        if (i)
            res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ )

            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main() {
    int T;
    scanf("%d", &T);

    while (T -- ) {
        scanf("%d%d%d", &n, &m, &k);
        memset(g, 0x3f, sizeof g);
        memset(st, false, sizeof st);

        while (m -- ) {
            int p, q, c;
            scanf("%d%d%d", &p, &q, &c);
            g[p][q] = g[q][p] = min(g[p][q], c);
        }

        while (k -- ) {
            memset(city, 0, sizeof city);
            int K;
            scanf("%d", &K);

            for (int i = 1; i <= K; i ++ )

                scanf("%d", &city[i]);

            for (int i = 1; i <= K; i ++ )

                for (int j = i + 1; j <= K; j ++ )

                    g[city[i]][city[j]] = g[city[j]][city[i]] = 0;
        }

        int ans = prim();

        if (ans == INF)
            puts("-1");
        else
            printf("%d\n", ans);
    }

    return 0;
}