找出最小生成树，同时用Max[i][j]记录i到j的唯一路径上最大边权。然后用不在最小生成树里的边i-j来替换，看看是否差值为0。
代码语言：javascript复制#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=101;
const int INF=0x3f3f3f3f;
int n,m,ans,s;
int lowc[N],vis[N],g[N][N];
int Max[N][N],fa[N],used[N][N];
int Prim(){
int ans=0;
memset(Max,0,sizeof Max);
memset(used,0,sizeof used);
memset(vis,0,sizeof vis);
vis[0]=1;
for(int i=1;i<n;i ){
lowc[i]=g[0][i];fa[i]=0;
}
for(int i=1;i<n;i ){
int p=0;
while(vis[p])p ;
for(int j=p 1;j<n;j )
if(!vis[j] && lowc[j]<lowc[p])
p=j;
if(lowc[p]==INF)return -1;//原图不连通
ans =lowc[p];
vis[p]=1;
used[p][fa[p]]=used[fa[p]][p]=1;
for(int j=0;j<n;j )
if(vis[j])
Max[j][p]=Max[p][j]=max(Max[j][fa[p]],lowc[p]); else if(g[p][j]<lowc[j]){
lowc[j]=g[p][j];
fa[j]=p;
}
}
return ans;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
memset(g,INF,sizeof g);
scanf("%d%d",&n,&m);
while(m--){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
u--;v--;
g[u][v]=g[v][u]=w;
}
ans=Prim();
s=INF;
for(int i=0;i<n;i )
for(int j=i 1;j<n;j )
if(g[i][j]!=INF&&!used[i][j])
s=min(s,g[i][j]-Max[i][j]);
if(ans==-1||s==0)
puts("Not Unique!");
else
printf("%dn",ans);
}
return 0;
}wa了好几发，原因是，s初始化为ans，而如果ans本身就是0的话，应该是唯一的最小生成树。
