本文共 1539 字，大约阅读时间需要 5 分钟。
标签：最小生成树
/* 题意：建立一个网络，要求每个结点都能与其他的结点连通，可通过一些中间结点间接连通。 要求the maximum length of a single cable is minimal，即网络中最长的一条网线是满足条件的最短的网线。 输出第一行为网络中的最大边权值，第二行为一个可行方案的边数k，下面k行为可行方案的k条边。 注意：所求网络不一定是最小生成树，如样例输出。 Special Judge，即不具有唯一解，可能有多解，样例输出为以下结果也可算对。1 13 31 2 1 31 3 2 43 4 2 3 思路：kruskal。 结果虽然不唯一，但是最小生成树一定是可行解之一，将边加入生成树时记录最大权值和边信息然后输出即可。*/#include#include #include using namespace std;#define maxn 15005typedef struct{ int x, y; int w;}edge;edge e[maxn], v[maxn];int rank_[maxn], father[maxn];int cmp(edge a, edge b){ return a.w < b.w;}void make_set(int x){ father[x] = x; rank_[x] = 0;}int find_set(int x){ return x != father[x] ? find_set(father[x]) : father[x];}void union_set(int x, int y){ // if(x == y) return ; if(rank_[x] > rank_[y]) father[y] = x; else{ if(rank_[x] == rank_[y]) rank_[y]++; father[x] = y; }}int main(){ int n, m, i, k, x, y, maxv; scanf("%d %d", &n, &m); for(i = 0; i < m; i++) scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].w); for(i = 0; i < n; i++) make_set(i); sort(e, e + m, cmp); k = 0, maxv = 0; for(i = 0; i < m; i++){ x = find_set(e[i].x), y = find_set(e[i].y); if(x != y){ union_set(x, y); v[k++] = e[i]; //保存边信息 if(maxv < e[i].w) maxv = e[i].w; //记录最大权值 } } printf("%d\n%d\n", maxv, k); for(i = 0; i < k; i++) printf("%d %d\n", v[i].x, v[i].y); return 0;}
转载地址：http://uskxi.baihongyu.com/