# POJ T1679 The Unique MST

xiaoxiao2021-03-01  11

# POJ T1679 The Unique MST

### 这里就用到了动态规划的思想，而Max这个数组就是用来记录最长边的，就是代码中的这句话：

Max[j][p] = Max[p][j] = max(dis[p],Max[j][pre[p]]);

### 代码：

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; #define MAXN 105 #define INF 0x3f3f3f3f int mst,smst; int n,m,maps[MAXN][MAXN],dis[MAXN]; int pre[MAXN],Max[MAXN][MAXN]; bool vis[MAXN],used[MAXN][MAXN]; void init(){ mst = 0; smst = INF; for(int i = 0; i <= n; ++i){ vis[i] = false; for(int j = 0; j <= i; ++j){ i == j ? maps[i][j] = 0 : maps[i][j] = maps[j][i] = INF; Max[i][j] = Max[j][i] = 0; used[i][j] = used[j][i] = false; } } } void Prim(int s){ vis[s] = true; for(int i = 1 ; i <= n; ++i){ dis[i] = maps[s][i]; pre[i] = s; } for(int i = 1; i < n; ++i){ int p = -1,minc = INF; for(int j = 1; j <= n; ++j) if(!vis[j] && dis[j] < minc){ minc = dis[j]; p = j; } vis[p] = true; mst += dis[p]; used[p][pre[p]] = used[pre[p]][p] = true; for(int j = 1; j <= n; ++j){ if(vis[j] && j != p) Max[j][p] = Max[p][j] = max(dis[p],Max[j][pre[p]]); //重点 if(!vis[j] && dis[j] > maps[p][j]){ dis[j] = maps[p][j]; pre[j] = p; } } } } void Second_tree(){ for(int i = 1; i <= n; ++i) for(int j = 1; j < i; ++j) if(!used[i][j] && maps[i][j] != INF) smst = min(smst,mst + maps[i][j] - Max[i][j]); //连接任意边，删除最长边 } int main(){ int t,a,b,c; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&m); init(); for(int i = 0; i < m; ++i){ scanf("%d%d%d",&a,&b,&c); maps[b][a] = maps[a][b] = min(maps[a][b],c); } Prim(1); Second_tree(); if(mst != smst) printf("%d\n",mst); else puts("Not Unique!"); } return 0; }