【题目链接】
【算法】
先求出图的最小生成树
枚举不在最小生成树上的边，若加入这条边，则形成了一个环，如果在环上且在最小生成树上的权值最大的边等于
这条边的权值，那么，显然最小生成树不唯一
树上倍增可以解决这个问题
【代码】
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; #define MAXN 110 #define MAXM 1000010 #define MAXLOG 20 struct Edge { int x,y; long long w; } edge[MAXM]; int T,n,m,i; long long val; vector< pair<int,long long> > e[MAXN]; bool on_mst[MAXM]; int fa[MAXN],anc[MAXN][MAXLOG],dep[MAXN]; long long mx[MAXN][MAXLOG]; bool not_unique; inline bool cmp(Edge a,Edge b) { return a.w < b.w; } inline int get_root(int x) { if (fa[x] == x) return x; return fa[x] = get_root(fa[x]); } inline void kruskal() { int i,x,y,sx,sy; long long w; for (i = 1; i <= n; i++) fa[i] = i; for (i = 1; i <= m; i++) on_mst[i] = false; sort(edge+1,edge+m+1,cmp); for (i = 1; i <= m; i++) { x = edge[i].x; y = edge[i].y; w = edge[i].w; sx = get_root(x); sy = get_root(y); if (sx != sy) { on_mst[i] = true; val += w; fa[sx] = sy; e[x].push_back(make_pair(y,w)); e[y].push_back(make_pair(x,w)); } } } inline void build(int u) { int i,v; for (i = 1; i < MAXLOG; i++) { anc[u][i] = anc[anc[u][i-1]][i-1]; mx[u][i] = max(mx[u][i-1],mx[anc[u][i-1]][i-1]); } for (i = 0; i < e[u].size(); i++) { v = e[u][i].first; if (anc[u][0] != v) { dep[v] = dep[u] + 1; anc[v][0] = u; mx[v][0] = e[u][i].second; build(v); } } } inline long long get(int x,int y) { int i,t; long long ans = 0; if (dep[x] > dep[y]) swap(x,y); t = dep[y] - dep[x]; for (i = 0; i < MAXLOG; i++) { if (t & (1 << i)) { ans = max(ans,mx[y][i]); y = anc[y][i]; } } if (x == y) return ans; for (i = MAXLOG - 1; i >= 0; i--) { if (anc[x][i] != anc[y][i]) { ans = max(ans,max(mx[x][i],mx[y][i])); x = anc[x][i]; y = anc[y][i]; } } return max(ans,max(mx[x][0],mx[y][0])); } int main() { scanf("%d",&T); while (T--) { scanf("%d%d",&n,&m); val = 0; not_unique = false; for (i = 1; i <= n; i++) { dep[i] = 0; e[i].clear(); memset(anc[i],0,sizeof(anc[i])); memset(mx[i],0,sizeof(mx[i])); } for (i = 1; i <= m; i++) scanf("%d%d%lld",&edge[i].x,&edge[i].y,&edge[i].w); kruskal(); build(1); for (i = 1; i <= m; i++) { if (!on_mst[i]) not_unique |= (get(edge[i].x,edge[i].y) == edge[i].w); } if (not_unique) printf("Not Unique! "); else printf("%lld ",val); } return 0; }