柿子合并

柿子合并

描述

又到了吃柿饼的季节。

小莉的果园共有 nn 棵柿子树，编号为 11 到 nn 。最开始，这些柿子树之间都没有道路相连。

小莉现在规划出了 mm 对中间可能修建双向道路的柿子树，用 mm 个三元

组 (u,v,w)(u,v,w) 表示，表示在编号为 uu 和 编号为 vv 的柿子树之间修建道路需要花费 ww 元。

小莉决定在修完道路后，将能够直接或间接通过道路连接的柿子树划分为一个子集。并 且，对于划分出的每一个子集，用这个子集中的所有式子树上长出的柿子做出一个柿饼。

小莉最终一共想要得到 kk 个柿饼，请你帮他计算最小的修路费用是多少。

输入

第 11 行有三个整数 nn， mm ， kk ，含义见题目描述。

接下来 mm 行，每行三个整数 uu ， vv ， ww ，描述每条可能修建的道路，含义如题所述。

输

输出一行一个整数，表示小莉修路的最小花费。

如果小莉无论如何都不能做出 kk 个柿饼，请输出 −1-1 。

输入样例 1

输样例 1

样例 1 解释

在 2，3 与 2，4 之间修建道路。

这样我们就可以将所有柿子制作成 22 个柿饼。

输入样例 2

点此下载。

限制

对于 30%的数据，1≤n≤100,1≤m≤10001≤n≤100,1≤m≤1000； 对于 100%的数据，

1≤n≤10000,1≤m≤100000,1≤k≤10,1≤u,v≤n,0≤w≤100001≤n≤10000,1≤m≤100

000,1≤k≤10,1≤u,v≤n,0≤w≤10000。

提示

[ 稍微改一下kruskal 算法就行辣]

代码

#include <iostream> #include<vector> #include<algorithm>

#pragma warning(disable:4996) using namespace std;

// ================= 代码实现开始 =================

/* 请在这里定义你需要的全局变量 */ const int N = 10000 + 7;

//表示一条情报struct Edge {

//表示将编号为u的柿子与编号为v的柿子合并为一颗柿子的花费为w

int u, v, w;

Edge(){}

Edge(int u,int v,int w):u(u),v(v),w(w){}

bool operator < (const Edge& A) const {

//按花费从小到大排序

return w < A.w;

}

};

//Father:每个节点的父亲节点int Father[N];

//查找节点x所在集合的根

//x:节点x

//返回值:根

int find(int x) {

int fx;//某节点的根节点(父节点)

if (Father[x] > 0)//若x的秩大于0，说明x不是根节点

{

fx = find(Father[x]);//若x不是根节点，则递归查找其根节点

Father[x] = fx;//*****此处至关重要，路径压缩，将某节点的父节点设置为根节点

********

return fx;

}

else

return x;//若x的秩小于等于0，说明x是根节点，返回x

}

void Union(int x, int y)//将x和y所在的两个集合合并

{

int fx = find(x);

int fy = find(y);

fy = fy;//断点调试点

if (fx == fy && fx != 0)//若fx和fy相等且其两个的秩不为0，则说明他们在同一个集合树中

return;

if (Father[fx] < Father[fy])

Father[fy] = fx;//若x所在的集合树比较高，则将y所在的树合并到x所在的树中，即将y

的根节点设置为fx

else if (Father[fx] == Father[fy])//若两个树的高度相等，则任意将一个树合并到另一个树中(此处是将x的根节点设置为fy)

{

Father[fy] -= 1;//合并后树的高度加一，故秩减一

Father[fx] = fy;

}

else//若y所在的集合树比较高，则将x所在的树合并到y所在的树中，即将x的根节点设置为fy

Father[fx] = fy;

}

// 给定n个点m条边的有权无向图，求最小的k-生成森林的边权和

// k-生成森林：k-生成森林是原图的一个生成子图，并且使得其中存在k个森林

// n：如题意

// m：如题意

// k：如题意

// E：大小为m的数组，表示m条情报

// 返回值：若能构成k-生成森林，则返回最小k-生成森林的边权和，否则返回-1 int getAnswer(int n, int m, int k, vector<Edge> E)

{

/* 请在这里设计你的算法 */

//ans:最小边权和

//edgeLft:k-生成森林中的边数

int ans = 0, edgeLft = n - k;

//初始化

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

Father[i] = 0;

}

//按花费大小从小到大排序

sort(E.begin(), E.end());

//指向E第一个元素的迭代器

vector<Edge>::iterator it = E.begin();

//若E中还有边或还未构成k-生成森林则重复以下操作

while (it != E.end() && edgeLft) {

int setu = find(it->u); //u所在的集合

int setv = find(it->v); //v所在的集合

if (setu != setv) {

Union(setu, setv); //若u,v不在同一个集合中，将u,v所在的集合合并

ans += it->w;     //将边权和(总花费)增加

edgeLft--;    //需要选取的边数减少1

}

it++;//迭代器后移

}

if (edgeLft)//若edgeLft>0，说明不存在k-生成森林，返回-1

return -1;

return ans;//若存在k-生成森林则返回边权和(总花费)

}

// ================= 代码实现结束 =================

int main()

{

int n, m, k;

vector<Edge> E;

scanf("%d%d%d", &n, &m, &k);

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

int u, v, w;

scanf("%d%d%d", &u, &v, &w);

E.push_back(Edge(u, v, w));

}

cout << getAnswer(n, m, k, E) << endl;

return 0;