Poj 1258: Agri-Net

poj1258.md

Poj 1258: Agri-Net

題目

分析

裸 MST。Kruskal 直接下了就是了

AC Code

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

struct Edge {
    int u, v, cost;

    bool operator < (const Edge& e) const {
        return cost < e.cost;
    }
};

int N, E;
Edge edges[10000];

int parent[100];
int height[100];

void init() {
    for (int i = 0; i < N; i++) {
        parent[i] = i;
        height[i] = 0;
    }
}

int find(int a) {
    if (parent[a] == a)
        return a;
    return parent[a] = find(parent[a]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;

    if (height[a] < height[b])
        parent[a] = b;
    else {
        parent[b] = a;
        if (height[a] == height[b])
            height[a]++;
    }
}

bool same(int a, int b) {
    return find(a) == find(b);
}

int kruskal() {
    sort(edges, edges + E);
    init();
    int ans = 0;
    for (int i = 0; i < E; i++) {
        Edge& e = edges[i];
        if (!same(e.u, e.v)) {
            unite(e.u, e.v);
            ans += e.cost;
        }
    }
    return ans;
}

int main() {
    while (scanf("%d", &N) != EOF) {
        int idx = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int w;
                scanf("%d", &w);
                if (i != j)
                    edges[idx++] = Edge{i, j, w};
            }
        }
        E = idx;

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

    return 0;
}