Description

最小生成樹(shù)大家都已經(jīng)很了解，次小生成樹(shù)就是圖中構(gòu)成的樹(shù)的權(quán)值和第二小的樹(shù)，此值也可能等于最小生成樹(shù)的權(quán)值和，你的任務(wù)就是設(shè)計(jì)一個(gè)算法計(jì)算圖的最小生成樹(shù)。

Input

存在多組數(shù)據(jù)，第一行一個(gè)正整數(shù)t，表示有t組數(shù)據(jù)。
每組數(shù)據(jù)第一行有兩個(gè)整數(shù)n和m（2<=n<=100），之后m行，每行三個(gè)正整數(shù)s，e，w，表示s到e的雙向路的權(quán)值為w。

Output

輸出次小生成樹(shù)的值，如果不存在輸出-1。

Sample Input

2 3 3 1 2 1 2 3 2 3 1 3 4 4 1 2 2 2 3 2 3 4 2 4 1 2

Sample Output

4 6

克魯斯卡爾算法。

求一次是最小生成樹(shù)，兩次就是次小生成數(shù)了。

//Asimple #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <cctype> #include <cstdlib> #include <stack> #include <cmath> #include <string> #include <queue> #define INF 100000 using namespace std; const int maxn = 210; typedef long long ll ; int fa[maxn];//并查集 int vis[maxn];//記錄下標(biāo) int path;//記錄最小生成樹(shù)用到邊的數(shù)量 int T, n, m; typedef struct node{int st;int ed;int w;bool operator < (const node& A) const {return w<A.w ;} }node; //初始化 void init(){//獲取并查集的大小 int len = sizeof(fa)/sizeof(fa[0]);for(int i=0; i<len; i++){fa[i] = i;} } //并查集的查找——查找父節(jié)點(diǎn) int findfa(int x){int pa;if( x == fa[x] ) return x;pa = findfa(fa[x]);fa[x] = pa;return pa; } //求最小生成樹(shù) int minTree(node *points, int m, int n) { init(); int i, count, flag, pa, pb; for (i = count = flag = path = 0; i < m; i ++) { pa = findfa(points[i].st); pb = findfa(points[i].ed); if (pa != pb) { vis[path ++] = i; fa[pa] = pb; count ++; } if (count == n - 1) { flag = 1; break; } } return flag; } // 求次小生成樹(shù) int secMinTree(node *points, int m, int n) { int i, j, min, tmp, pa, pb, count, flag; for (i = 0, min = INF; i < path; i ++) { init(); // 求次小生成樹(shù) for (j = count = tmp = flag = 0; j < m; j ++) { if (j != vis[i]) { pa = findfa(points[j].st); pb = findfa(points[j].ed); if (pa != pb) { count ++; tmp += points[j].w; fa[pa] = pb; } if (count == n - 1) { flag = 1; break; } } } if (flag && tmp < min) min = tmp; } min = (min == INF) ? -1 : min; return min; } int main(){node *p;scanf("%d",&T);while( T -- ){scanf("%d %d",&n, &m);p = (node *)malloc(sizeof(node) * m);for(int i=0; i<m; i++){scanf("%d %d %d",&p[i].st,&p[i].ed,&p[i].w);}sort(p,p+m);int f = minTree(p,m,n);if( f == 0 ){//無(wú)法生成最小生成樹(shù)printf("-1\n");continue; } else {int Min = secMinTree(p,m,n);printf("%d\n",Min);}//釋放p free(p);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Asimple/p/5715563.html

總結(jié)

以上是生活随笔為你收集整理的ACM题目————次小生成树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。