1349：【例410】最优布线问题

【题目描述】

学校有nn台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。

当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。

现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。

【输入】

第一行为整数nn（2≤n≤1002≤n≤100），表示计算机的数目。此后的nn行，每行nn个整数。第x+1x+1行yy列的整数表示直接连接第xx台计算机和第yy台计算机的费用。

【输出】

一个整数，表示最小的连接费用。

【输入样例】

3
0 1 2
1 0 1
2 1 0

【输出样例】

2

【提示】

注：表示连接11和22，22和33，费用为2

#include <bits/stdc++.h>
using namespace std;

struct Node { // 边[x,y]权重w
    int x, y, w;

    Node(int x, int y, int w)
    {
        this->x = x;
        this->y = y;
        this->w = w;
    }
};

bool cmp(const Node &a, const Node &b)
{ // 边的比较，小的在前
    return (a.w < b.w);
}

void init(vector<int> &da)
{ // 并查集的初始化
    for (int i = 0; i < da.size(); i++) {
        da[i] = i;
    }
}

int find(vector<int> &da, int x)
{ // 并查集的查找
    if (da[x] != x) {
        da[x] = find(da, da[x]);
    }
    return da[x];
}

bool united(vector<int> &da, int x, int y)
{ // 并查集的判断
    int xda = find(da, x);
    int yda = find(da, y);
    return (xda == yda);
}

void unite(vector<int> &da, int x, int y)
{ // 并查集的合并
    int xda = find(da, x);
    int yda = find(da, y);
    if (xda != yda) {
        da[xda] = yda;
    }
}

int kruskal(vector<Node> &es, int n)
{ // 克鲁斯卡尔算法
    int ans = 0; // 答案
    vector<int> da(n + 1); // 并查集
    init(da); // 初始化并查集
    sort(es.begin(), es.end(), cmp);
    for (auto &e : es) { // 遍历所有边
        if (united(da, e.x, e.y)) {
            continue; // 能形成环
        }
        // cout << e.x << "," << e.y << endl;
        unite(da, e.x, e.y);
        ans += e.w;
    }
    return ans;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    int n, w; // 节点数n, 权重w
    scanf("%d", &n);
    vector<Node> es; // 边集
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d%", &w);
            if (w > 0 && i < j) { // 非0
                es.push_back(Node(i, j, w));
            }
        }
    }
    int ans = kruskal(es, n);
    printf("%d\n", ans);
    return 0;
}