POJ_1679
这个题目可以先用prim求一棵最小生成树，然后顺便更新出书上两点间的最大边权。
之后枚举每一条边，如果这条边没有在生成树上，且生成树上这两点间的最大边权与之相等，那么就说明这条边也可以作为最小生成树边，因此最小生成树就不唯一了。
#include<stdio.h> #include<string.h> #define MAXD 110 #define MAXM 100010 #define INF 0x3f3f3f3f int N, M, first[MAXD], e, next[MAXM], v[MAXM], dis[MAXD], pre[MAXD], vis[MAXD], g[MAXD][MAXD], max[MAXD][MAXD]; void init() { int i, x, y, z; scanf("%d%d", &N, &M); memset(g, 0x3f, sizeof(g)); for(i = 0; i < M; i ++) { scanf("%d%d%d", &x, &y, &z); g[x][y] = g[y][x] = z; } } void add(int x, int y) { v[e] = y; next[e] = first[x], first[x] = e ++; } void dfs(int cur, int fa, int k, int m) { int i; max[cur][k] = max[k][cur] = m; for(i = first[cur]; i != -1; i = next[i]) if(v[i] != fa) dfs(v[i], cur, k, m > max[cur][v[i]] ? m : max[cur][v[i]]); } int intree(int x, int y) { int i; for(i = first[x]; i != -1; i = next[i]) if(v[i] == y) return 1; return 0; } int isunique() { int i, j, k; for(i = 1; i <= N; i ++) for(j = i + 1; j <= N; j ++) if(g[i][j] != INF && !intree(i, j) && g[i][j] == max[i][j]) return 0; return 1; } void solve() { int i, j, k, m, ans = 0; memset(first, -1, sizeof(first)); e = 0; memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); dis[1] = 0, vis[1] = 1; for(i = 2; i <= N; i ++) if(g[1][i] < dis[i]) dis[i] = g[1][i], pre[i] = 1; for(i = 1; i < N; i ++) { m = INF; for(j = 1; j <= N; j ++) if(!vis[j] && dis[j] < m) m = dis[k = j]; ans += m, vis[k] = 1; for(j = 1; j <= N; j ++) if(!vis[j] && g[k][j] < dis[j]) dis[j] = g[k][j], pre[j] = k; add(pre[k], k), add(k, pre[k]); dfs(pre[k], k, k, m); } if(isunique()) printf("%d\n", ans); else printf("Not Unique!\n"); } int main() { int t; scanf("%d", &t); while(t --) { init(); solve(); } return 0; }