又是一个上百行代码的题……

这个题要求判断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;
}

• 相关文章
• 全局相关文章