柿子合并发表时间：2022-10-27 20:38 柿子合并 描述 又到了吃柿饼的季节。 小莉的果园共有 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; |