首页 > 代码库 > poj 1679 The Unique MST 【次小生成树】【模板】
poj 1679 The Unique MST 【次小生成树】【模板】
题目:poj 1679 The Unique MST
题意:给你一颗树,让你求最小生成树和次小生成树值是否相等。
分析:这个题目关键在于求解次小生成树。
方法是,依次枚举不在最小生成树上的边,然后添加到最小生成树上,然后把原树上添加了之后形成环的最长的边删去,知道一个最小的。就是次小生成树。
这些需要的都可以在求解最小生成树的时候处理出来。
AC代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <string> #include <vector> #define Del(a,b) memset(a,b,sizeof(a)) using namespace std; const int inf = 0x3f3f3f3f; const int N = 550; int mp[N][N]; bool vis[N],used[N][N]; int pre[N],ma[N][N],cost[N]; int n,m; int Prim(int x) { int ans = 0; Del(ma,0); Del(used,false); for(int i=1;i<=n;i++) { cost[i] = mp[x][i]; pre[i] = 1; vis[i] = false; } vis[x] = true; pre[x] = -1; for(int i=1;i<n;i++) { int minc = inf; int p = -1; for(int j=1;j<=n;j++) { if(vis[j]==false && minc>cost[j]) { minc = cost[j]; p = j; } } if(p==-1) return -1; ans+=minc; vis[p] = true; int tmp = pre[p]; used[p][tmp] = used[tmp][p] = true; //MST上的边 for(int j=1;j<=n;j++) { if(vis[j]) ma[j][p] = ma[p][j] = max(ma[j][tmp],cost[p]); if(vis[j]==false && cost[j]>mp[p][j]) { cost[j] = mp[p][j]; pre[j] = p; } } } return ans; } int Next_Prim(int x) { int ans = inf; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(mp[i][j]!=inf && !used[i][j]) //枚举不在MST上的边替换 ans = min(ans,x+mp[i][j]-ma[i][j]); } } return ans; } int main() { int T; scanf("%d",&T); while(T--) { memset(mp,inf,sizeof(mp)); scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); mp[x][y] = mp[y][x] = z; } int ans = Prim(1); int next = Next_Prim(ans); //printf("%d %d\n",ans,next); if(ans!=next) puts("No"); else puts("Yes"); } return 0; }
poj 1679 The Unique MST 【次小生成树】【模板】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。