最小生成树 -> 最小生成图

作者: 腹黑猫 分类: 文章 发布时间: 2015-03-27 19:59

原题:Vijos 1579

克鲁斯卡尔的应用,想来也是极有意思的一道题(×)。


u, v 为最小生成树中直接相连的两个节点,
W 为边 u,v 的权值。
ChildrenNum[u] 为 u 的子节点数。
分析
u, v 已经在最小生成树中已经直接相连,那在完全图中,其他连通 u, v 的路径的权值一定会大于 W ,我们在连接他们的时候,他们的权值应该都为 W + 1
这样才能保证他们相连后的权值最小,构成最小生成图。
而 u,v 之间最多可以连 Q = ChildrenNum[u] * ChildrenNum[v] 条边,想要构成最小生成图,还需要连 Q – 1 条边,每条边的权值为 W + 1。
代码:

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

const int MAXN = 20001;

struct Edge{
    long long From, To, Value;
    bool operator < (const Edge& b) const {
        return Value < b.Value;
    }
};

vector<Edge> Edges;
int Father[MAXN];
int ChildrenNum[MAXN];
int n;
long long Ans = 0;

int GetFather(int x){
    return Father[x] == x ? x : Father[x] = GetFather(Father[x]);
}

void SetFather(int x, int y){
    ChildrenNum[x] += ChildrenNum[y];
    Father[GetFather(y)] = GetFather(Father[x]);
}

void Init(){
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i < n; ++i){
        long long from, to, value;
        cin >> from >> to >> value;
        Edges.push_back((Edge){from, to, value});
        Father[i] = i;
        ChildrenNum[i] = 1;
    }
    Father[n] = n;
    ChildrenNum[n] = 1;
    sort(Edges.begin(), Edges.end());
}

void Kruskal(){
    for (int i = 0; i < n - 1; ++i){
        int FatherA = GetFather(Edges[i].From);
        int FatherB = GetFather(Edges[i].To);
        Ans += Edges[i].Value + (ChildrenNum[FatherA] * ChildrenNum[FatherB] - 1) * (Edges[i].Value + 1);
        SetFather(FatherA, FatherB);
    }
    cout << Ans;
}

int main(int argc, char const *argv[]){
    Init();
    Kruskal();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

标签云