题意：求次小生成树，若权值和与最小生成树相等，输出"Not Unique!" ；否则，输出mst
/* 次小生成树 首先明白一点，次小生成树是由最小生成树改变一条边得来的，然后我们就可以先求出最小生成树， 然后枚举没在最小生成树中的边(x、y、z)，用这条边来替换树中x、y之间的一条边，很显然，替换 时应该替换x、y中的最长边，所以可以预处理出树中x、y之间的最长边。 */ #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define N 110 #define INF 1000000000 using namespace std; int head[N],g[N][N],fa[N],vis[N*N],n,m,cnt,mst; struct node { int x,y,z; };node ee[N*N]; struct Node { int v,pre,t; };Node e[N*2]; bool cmp(const node&s1,const node&s2) { return s1.z<s2.z; } int find(int x) { if(fa[x]==x)return x; return fa[x]=find(fa[x]); } void add(int x,int y,int z) { ++cnt; e[cnt].v=y; e[cnt].t=z; e[cnt].pre=head[x]; head[x]=cnt; } void dfs(int s,int now,int from,int mmx) { g[s][now]=mmx; for(int i=head[now];i;i=e[i].pre) if(e[i].v!=from) dfs(s,e[i].v,now,max(mmx,e[i].t)); } void work() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&ee[i].x,&ee[i].y,&ee[i].z); } sort(ee+1,ee+m+1,cmp); for(int i=1;i<=m;i++) { int a=find(ee[i].x),b=find(ee[i].y); if(a!=b) { fa[a]=b;mst+=ee[i].z;vis[i]=1; add(ee[i].x,ee[i].y,ee[i].z); add(ee[i].y,ee[i].x,ee[i].z); } } for(int i=1;i<=n;i++) dfs(i,i,-1,0); int ans=INF; for(int i=1;i<=m;i++) if(!vis[i]) ans=min(ans,mst-ee[i].z+g[ee[i].x][ee[i].y]); if(ans==mst)printf("Not Unique! "); else printf("%d ",mst); } int main() { int T;scanf("%d",&T); while(T--) { memset(g,0,sizeof(g)); memset(fa,0,sizeof(fa)); memset(head,0,sizeof(head)); memset(vis,0,sizeof(vis)); mst=cnt=0; work(); } return 0; }