题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=17124
题目描述：就是求次小生成树，若次小生成树与最小生成树相等则输出 Not Unique! 否则输出最小生成树权值和。
题目思路：就是运用次小生成树算法
AC代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson root<<1,l,mid #define rson root<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) using namespace std; #define gamma 0.5772156649015328606065120 //欧拉常数 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 100001 #define maxn 1000100 typedef long long LL; typedef pair<int,int> PII; int pic[101][101],tans,used[101][101],path[101][101],n; ///used数组判断两点之间直接相连的边是否使用过，path数组记录最小生成树中点i到点j最大的边权值 int prim() { int i,j,d[101],vis[101],ans=0,pre[101]; ///pre数组记录父节点 memset(vis,0,sizeof(vis)); memset(path,0,sizeof(path)); for(i=0; i<n; ++i) d[i]=pic[0][i],pre[i]=0; vis[0]=1; for(i=1; i<n; ++i) { int m=inf,u; for(j=1; j<n; ++j) if(!vis[j]&&d[j]<m) m=d[u=j]; vis[u]=1; used[u][pre[u]]=used[pre[u]][u]=1; ans+=m; for(j=1; j<n; ++j) { if(vis[j]) { path[j][u]=path[u][j]=max(d[u],path[j][pre[u]]); ///比较过程d[u]是生成树到u的值，path[j][pre[u]]是连接u点的父节点到j的权值 } ///path数组更新过程类似DP过程 if(!vis[j]&&d[j]>pic[u][j]) { d[j]=pic[u][j]; pre[j]=u; } } } return ans; } int t_prim(int &v) { int i,j,ans=inf; for(i=0; i<n; ++i) for(j=i+1; j<n; ++j) { if(!used[i][j]) ans=min(v+pic[i][j]-path[i][j],ans); } return ans; } int main() { int pos,group,x,y,v,Case=0; int i,j,m,_ans,k; scanf("%d",&group); while(group--) { scanf("%d%d",&n,&m); memset(pic,inf,sizeof(pic)); memset(used,0,sizeof(used)); for(i=0; i<m; ++i) { scanf("%d%d%d",&x,&y,&v); pic[x-1][y-1]=pic[y-1][x-1]=v; } _ans=prim(); tans=t_prim(_ans); if(tans==_ans) printf("Not Unique! "); else printf("%d ",_ans); } return 0; }