最小生成树 -> 最小生成图
原题：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;
}
#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;
}