题意就是求一个MST，然后求一个次小生成树(可能与MST相等)，然后问我们这个次小生成树是否与MST的总权重相等。
朴素的想法是求出一个MST后把它上面的每个边删一次(一次就够，因为次小生成树如果存在必然与MST有n-1条公共边)，删后再求一次MST，然而求 n-1 次 MST明显不实际。
我们转换一下思路，不是删掉边加边而是替换边，假设加的边是 G[i][j] (没用过的)那么被替换的边一定是MST上 i -> j 的路径中最大的边(否则得到一定不是次小生成树)，如此只要在求一次MST的基础上多加O(n^2)。
为了达到这个目的我们需要用prim在求MST的同时处理处path[i][j]。具体参见代码。
if(vis[j]&&u!=j)//path[u][j] means the longest edges of the path from u to j
path[j][u]=path[u][j]=max(path[j][pre[u]],dist[u]);
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <vector> 5 #include <utility> 6 7 using namespace std; 8 #define fst first 9 #define scd second 10 #define pb(x) push_back((x)) 11 #define mkp(x,y) make_pair((x),(y)) 12 #define ist(x) insert((x)) 13 typedef long long ll; 14 typedef pair<int ,int > pii; 15 typedef pair<ll ,ll > pll; 16 typedef vector< int > vi; 17 ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);} 18 ll qPow(ll a,ll b,ll mod){ ll ret=1ll;while(b){ if(b&1) ret=ret*a%mod;a=a*a%mod;b>>=1;} return ret; } 19 20 const int INF=0x3f3f3f3f; 21 int n,m;// number of V and E 22 int G[128][128]; 23 bool vis[128],used[128][128]; 24 int path[128][128],dist[128]; 25 int pre[128]; 26 27 int prim(int v){// v is start 28 memset(vis,false,sizeof(vis)); 29 memset(used,false,sizeof(used));// 30 memset(path,0,sizeof(path));// 31 for(int i=1;i<=n;++i){ 32 dist[i]=G[v][i]; 33 pre[i]=v; 34 } 35 vis[v]=true; 36 37 int sum=0; 38 int u,tmp;// u is index of tmp dot 39 for(int i=1;i<n;++i){// n-1 edges 40 u=v; 41 tmp=INF; 42 for(int j=1;j<=n;++j){// find the nearest vertex 43 if(!vis[j]&&dist[j]<tmp){ 44 tmp=dist[j]; 45 u=j; 46 } 47 } 48 vis[u]=true; 49 sum+=dist[u]; 50 used[u][pre[u]]=used[pre[u]][u]=true; 51 52 for(int j=1;j<=n;++j){ 53 if(vis[j]&&u!=j)//path[u][j] means the longest edges of the path from u to j 54 path[j][u]=path[u][j]=max(path[j][pre[u]],dist[u]); 55 if(!vis[j]&&dist[j]>G[u][j]){//relax 56 dist[j]=G[u][j]; 57 pre[j]=u;// 58 } 59 } 60 } 61 return sum; 62 } 63 64 int second_MST(int tot) { 65 int ans=INF; 66 //puts("test in second_MST: "); 67 for(int i=1;i<=n;++i){ 68 for(int j=1;j<=n;++j){ 69 //printf("%d %d : used=%d , path=%d ,G=%d ",i,j,used[i][j]?1:0,path[i][j],G[i][j]); 70 if(!used[i][j]&&i!=j) 71 ans=min(ans,tot-path[i][j]+G[i][j]); 72 } 73 } 74 return ans; 75 } 76 77 int main(){ 78 int Test; 79 scanf("%d",&Test); 80 while(Test--) { 81 scanf("%d%d",&n,&m); 82 83 // initial 84 for(int i=1;i<=n;++i) 85 for(int j=1;j<=n;++j) G[i][j]=INF; 86 87 for(int i=0;i<m;++i){ 88 int u,v,w; 89 scanf("%d%d%d",&u,&v,&w); 90 G[u][v]=w,G[v][u]=w; 91 } 92 93 int tot = prim(1); 94 int ans=second_MST(tot); 95 //printf("tot and ans : %d , %d ",tot,ans); 96 if(ans==tot) puts("Not Unique!"); 97 else printf("%d ",tot); 98 } 99 return 0; 100 }