http://poj.org/problem?id=1679

題解：次小生成樹

C++版本一

Prim算法

/* *@Author: STZG *@Language: C++ */ //#include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v; int ans,cnt,flag,temp,sum; int mapp[N][N]; bool vis[N],connect[N][N]; int dis[N],maxd[N][N],per[N]; void Init() {memset(mapp,INF,sizeof(mapp));memset(connect,false,sizeof(connect)); } int prim() {memset(maxd,0,sizeof(maxd));memset(vis,false,sizeof(vis));for(int i = 1;i <= n;i ++){dis[i] = mapp[1][i];per[i] = 1;//首先父親節點都是根節點}vis[1] = 1;dis[1] = 0;int res = 0;for(int i = 1;i < n;i ++){int index = -1,temp = INF;for(int j = 1;j <= n;j ++){if(!vis[j] && dis[j] < temp){index = j;temp = dis[j];}}if(index == -1) return res;vis[index] = 1;connect[index][per[index]] = false;connect[per[index]][index] = false;//這條邊已經在最小生成樹中，后面我們就不能添加這條邊了res += temp;maxd[per[index]][index]=maxd[index][per[index]]=temp;//更新點之間的最大值for(int j=1;j<=n;j++){if(j != index && vis[j]){//只是更新我們已經遍歷過來的節點maxd[index][j]=maxd[j][index]=max(maxd[j][per[index]],dis[index]);}if(!vis[j] && mapp[index][j] < dis[j]){dis[j] = mapp[index][j];per[j] = index;}}}return res; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);//while(t--){int T;scanf("%d\n",&T);while(T--){scanf("%d%d",&n,&m);Init();int u,v,w;for(int i = 0;i < m;i ++){scanf("%d%d%d",&u,&v,&w);mapp[u][v] = w;mapp[v][u] = w;connect[u][v] = true;connect[v][u] = true;}int ans = prim();bool over = false;//如果有某條邊沒有被最小生成樹使用，并且i~j的最大值大于圖中得到最大值，那么就表示次小生成樹存在//相反就不會存在for(int i = 1;!over && i <= n;i ++)for(int j = 1;j <= n;j ++){if(connect[i][j] == false || mapp[i][j] == INF)continue;if(mapp[i][j] == maxd[i][j])//當邊長度相同是就是表示最小生成樹相同{over = 1;break;}}if(over)printf("Not Unique!\n");elseprintf("%d\n",ans);}//如果我們需要求解次小生成樹的權值時，我們就要把在最小生成樹中沒有用過的邊，加上然后減去對應環中最大的路徑//}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

C++版本二

#include<stdio.h> #include<string.h> #include<algorithm> #define ll long long #define pb push_back #define INF 0x3f3f3f3f #define FI first #define SE second #define MP make_pair #define PI pair<int,int> #define lson l,m,rt<<1,ls,rs #define rson m+1,r,rt<<1|1,ls,rs #define test printf("here!!!\n") using namespace std; const int mx=100+10; int n,m; int dis[mx]; int vis[mx]; int mp[mx][mx]; int sum; int maxd[mx][mx]; int pre[mx]; int connect[mx][mx]; void prim() {sum=0;memset(maxd,0,sizeof(maxd));memset(connect,0,sizeof(connect));for (int i=1;i<=n;++i){dis[i]=mp[1][i];pre[i]=1;vis[i]=0;}dis[1]=0;vis[1]=1;int now=1;for (int i=1;i<n;++i){int minn=INF;for (int j=1;j<=n;++j){if (!vis[j]&&minn>dis[j]){minn=dis[j];now=j;}}sum+=dis[now];vis[now]=1;connect[now][pre[now]]=connect[pre[now]][now]=1;for (int j=1;j<=n;++j){if (vis[j]){maxd[j][now]=maxd[now][j]=max(maxd[j][pre[now]],dis[now]);}else if (dis[j]>mp[now][j]){dis[j]=mp[now][j];pre[j]=now;}}} } int sprim() {int ans=INF;for (int i=1;i<=n;++i){for (int j=i+1;j<=n;++j){if (!connect[i][j]&&mp[i][j]!=INF){ans=min(ans,sum+mp[i][j]-maxd[i][j]);}}}return ans; } int main() {int x,y,w,t;scanf("%d",&t);while (t--){memset(mp,INF,sizeof(mp));scanf("%d%d",&n,&m);for (int i=1;i<=m;++i){scanf("%d%d%d",&x,&y,&w);mp[x][y]=w;mp[y][x]=w;}prim();int res=sprim();if (sum==res) printf("Not Unique!\n");else printf("%d\n",sum);} }

C++版本三

Kruskal算法

#include<stdio.h> #include<string.h> #include<algorithm> #define ll long long #define pb push_back #define INF 0x3f3f3f3f #define FI first #define SE second #define MP make_pair #define PI pair<int,int> #define lson l,m,rt<<1,ls,rs #define rson m+1,r,rt<<1|1,ls,rs #define test printf("here!!!\n") using namespace std; const int mx=1e4+10; const int MX=5e3+10; int n,m; struct Node {int st;int to;ll w;friend bool operator <(const Node &a,const Node &b){return a.w<b.w;} }vec[MX]; int use[MX]; int pre[mx],sz[mx]; int fa[mx][20]; int ma[mx][20]; int lg[mx]; int dis[mx]; int vis[mx]; struct Eg {int to;ll w;int nxt; }edge[MX*2]; int head[mx]; int cnt=0; ll sum=0; void add(int u,int v,ll w) {edge[++cnt].to=v;edge[cnt].w=w;edge[cnt].nxt=head[u];head[u]=cnt; } void init() {cnt=0;sum=0;lg[0]=-1;for (int i=1;i<=n;++i) lg[i]=lg[i>>1]+1;for (int i=1;i<=n;++i){head[i]=0,dis[i]=0,vis[i]=0,pre[i]=i,sz[i]=1;}memset(ma,0,sizeof(ma));memset(fa,0,sizeof(fa));memset(use,0,sizeof(use));dis[0]=-1; } int unfd(int x) {int r=x;while (r!=pre[r]) r=pre[r];int t;while (x!=pre[x]){t=pre[x];pre[x]=r;x=t;}return r; } int unjoin(int x,int y) {int fx=unfd(x),fy=unfd(y);if (fx!=fy){if (sz[fx]<sz[fy]){pre[fx]=fy;sz[fy]+=sz[fx];}else{pre[fy]=fx;sz[fx]+=sz[fy];}return 1;}return 0; } void kruskal() {int tot=n-1;for (int i=1;i<=m;++i){if (unjoin(vec[i].st,vec[i].to)){--tot;sum+=vec[i].w;use[i]=1;add(vec[i].st,vec[i].to,vec[i].w);add(vec[i].to,vec[i].st,vec[i].w);}if (!tot) break;} } void dfs(int st,int fath) {vis[st]=1;dis[st]=dis[fath]+1;fa[st][0]=fath;for (int i=1;(1<<i)<=dis[st];++i){fa[st][i]=fa[fa[st][i-1]][i-1];ma[st][i]=max(ma[st][i-1],ma[fa[st][i-1]][i-1]);}for (int i=head[st];i;i=edge[i].nxt){if (!vis[edge[i].to]){ma[edge[i].to][0]=edge[i].w;dfs(edge[i].to,st);}} } int LCA(int u,int v) {int maxn=0;if (dis[u]<dis[v]) swap(u,v);while (dis[u]>dis[v]){int loog=lg[dis[u]-dis[v]];maxn=max(ma[u][loog],maxn);u=fa[u][loog];}if (u==v) return maxn;for (int i=lg[dis[u]];i>=0;--i){if (fa[u][i]!=fa[v][i]){maxn=max(max(ma[u][i],ma[v][i]),maxn);u=fa[u][i];v=fa[v][i];}}return max(max(ma[u][0],ma[v][0]),maxn); } int main() {int t;scanf("%d",&t);while (t--){scanf("%d%d",&n,&m);int x,y;ll z;init();for (int i=1;i<=m;++i){scanf("%d%d%lld",&vec[i].st,&vec[i].to,&vec[i].w);}sort(vec+1,vec+m+1);kruskal();dfs(1,0);ll ans=0x3f3f3f3f3f3f3f3f;for (int i=1;i<=m;++i){if (!use[i]){ans=min(ans,sum-LCA(vec[i].st,vec[i].to)+vec[i].w);}}if (ans==sum) printf("Not Unique!\n");else printf("%lld\n",sum);} }

C++版本四

#include <vector> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define INF 0x3f3f3f3fusing namespace std; int n,m; struct data {int u,v,w;bool vis; } p[20010]; vector<int>G[110]; int per[110],maxd[110][110]; bool cmp(data a,data b) {return a.w < b.w; } int Union_Find(int x) {return x == per[x] ? x: per[x] = Union_Find(per[x]); } void kruskal() {sort(p,p+m,cmp);for(int i=0; i<=n; i++)//初始化{G[i].clear();G[i].push_back(i);per[i]=i;}int sum=0,k=0;//sum是最小生成樹的值for(int i=0; i<m; i++){if(k==n-1) break;int x1=Union_Find(p[i].u),x2=Union_Find(p[i].v);if(x1!=x2){k++;p[i].vis=1;//這條邊已經用過了sum+=p[i].w;int len_x1=G[x1].size();int len_x2=G[x2].size();for(int j=0; j<len_x1; j++)//更新兩點之間距離的最大值for(int k=0; k<len_x2; k++)maxd[G[x1][j]][G[x2][k]]=maxd[G[x2][k]][G[x1][j]]=p[i].w;//因為后面的邊會越來越大，所以這里可以直接等于當前邊的長度per[x1]=x2;//因為per[x1] = x2,在Union_Find函數中要尋找和x1相關聯節點的跟節點的時候，都會找到x2，所以這里不用再去更新和x1節點相連的節點//十分感謝Self-Discipline博主，提出此問題 // int tem[110]; // for(int j=0; j<len_x2; j++)//現在已經屬于一棵樹了，那么我們就將點添加到相應的集合中 // tem[j]=G[x2][j];for(int j=0; j<len_x1; j++)G[x2].push_back(G[x1][j]); // for(int j=0; j<len_x2; j++) // G[x1].push_back(tem[j]);}}int cisum=INF;//次小生成樹的權值for(int i=0; i<m; i++)if(!p[i].vis)cisum=min(cisum,sum+p[i].w-maxd[p[i].u][p[i].v]);if(cisum>sum)printf("%d\n",sum);elseprintf("Not Unique!\n"); } int main() {int T;scanf("%d\n",&T);while(T--){scanf("%d%d",&n,&m);for(int i=0; i<m; i++){scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w);p[i].vis = false;}kruskal();}return 0; }

?

總結

以上是生活随笔為你收集整理的The Unique MST的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。