[POJ 1679]The Unique MST
又是一个上百行代码的题……
这个题要求判断MST的唯一性。我们可以通过求非严格的次小生成树,来判断MST的唯一性。
非严格的次小生成树就是枚举考虑将MST外的哪条边加入替换MST中的一条边。替换的方法是,求出MST中待加入边两端路径上最大边,删掉之后再把待加入边加进去。假如有一个非严格次小生成树权值和和MST一样,就说明MST不唯一。
代码:
#include <cstdio> #include <cstring> #include <bitset> #include <algorithm> using namespace std; const int maxn=105,maxm=10005; #define REP(i,n) for(i=1;i<=(n);i++) #define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i]) #define CL_ARR(x,v) memset(x,v,sizeof(x)) int first[maxn]; int next[205],to[205],dist[205]; int graph_cnt=0; inline void AddEdge(int u,int v,int d){ graph_cnt++; next[graph_cnt]=first[u]; first[u]=graph_cnt; to[graph_cnt]=v; dist[graph_cnt]=d; } inline void ClearGraph(){ CL_ARR(first,0); CL_ARR(next,0); CL_ARR(to,0); CL_ARR(dist,0); graph_cnt=0; } int anc[maxn][32],maxcost[maxn][32]; int dep[maxn]; void dfs(int x,int depth,int fa,int d){ int i; dep[x]=depth; anc[x][0]=fa; maxcost[x][0]=d; GRAPH_REP(i,x){ if(to[i]!=fa){ dfs(to[i],depth+1,x,dist[i]); } } } int n; inline void process(){ register int i,j,a; dfs(1,0,0,0); for(j=1;(1<<j)<n;j++){ REP(i,n){ if(anc[i][j-1]!=-1){ a=anc[i][j-1]; anc[i][j]=anc[a][j-1]; maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]); } } } } int query(int x,int y){ register int tmp,log,i,ans=-0x7fffffff; if(dep[x]<dep[y]) swap(x,y); for(log=1;(1<<log)<=dep[x];log++); log--; for(i=log;i>=0;i--) if(dep[x]-(1<<log)>=dep[y]){ ans=max(ans,maxcost[x][i]); x=anc[x][i]; } if(x==y) return ans; for(i=log;i>=0;i--) if(anc[x][i]!=-1 && anc[x][i]!=anc[y][i]){ ans=max(ans,maxcost[x][i]); x=anc[x][i]; ans=max(ans,maxcost[y][i]); y=anc[y][i]; } ans=max(ans,maxcost[x][0]); ans=max(ans,maxcost[y][0]); return ans; } int p[maxn],rank[maxn]; int find_set(int x){ if(p[x]==x) return x; else return p[x]=find_set(p[x]); } void link_set(int x,int y){ if(rank[x]>rank[y]){ p[y]=x; }else{ p[x]=y; if(rank[x]==rank[y]) rank[y]++; } } inline void union_set(int x,int y){ link_set(find_set(x),find_set(y)); } inline bool is_same(int x,int y){ return find_set(x)==find_set(y); } inline void init_set(){ register int i; REP(i,n) p[i]=i; CL_ARR(rank,0); } struct Edge{ int u,v,d; bool operator <(const Edge& x) const{ return d<x.d; } }; #define ALL_FT(x) E[x].u,E[x].v Edge E[maxm]; int m; bitset<maxn> Choose; int MST(){ register int i,ans=0,cnt=0; ClearGraph(); init_set(); Choose.reset(); sort(E+1,E+1+m); REP(i,m){ if(!is_same(ALL_FT(i))){ Choose[i]=true; cnt++; ans+=E[i].d; union_set(ALL_FT(i)); AddEdge(ALL_FT(i),E[i].d); AddEdge(E[i].v,E[i].u,E[i].d); } if(cnt==(n-1)){ break; } } return ans; } int main(){ int T; int u,v,d; register int i,ans,temp; bool OK; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); REP(i,m){ scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].d); } ans=MST(); CL_ARR(anc,-1); process(); OK=true; REP(i,m){ if(!Choose[i]){ temp=query(ALL_FT(i)); if(temp==E[i].d){ OK=false; puts("Not Unique!"); break; } } } if(OK) printf("%d\n",ans); } return 0; }