The Unique MST

http://poj.org/problem?id=1679
次の小さい木を生成します。
C++バージョン1
Primアルゴリズム

/*
*@Author:   STZG
*@Language: C++
*/
//#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

C++バージョン2

#include
#include
#include
#define ll long long
#define pb push_back
#define INF 0x3f3f3f3f
#define FI first
#define SE second
#define MP make_pair
#define PI pair
#define lson l,m,rt<<1,ls,rs
#define rson m+1,r,rt<<1|1,ls,rs
#define test printf("here!!!
")
using namespace std;
const int mx=100+10;
int n,m;
int dis[mx];
int vis[mx];
int mp[mx][mx];
int sum;
int maxd[mx][mx];
int pre[mx];
int connect[mx][mx];
void prim()
{
    sum=0;
    memset(maxd,0,sizeof(maxd));
    memset(connect,0,sizeof(connect));
    for (int i=1;i<=n;++i)
    {
        dis[i]=mp[1][i];
        pre[i]=1;
        vis[i]=0;
    }
    dis[1]=0;
    vis[1]=1;
    int now=1;
    for (int i=1;idis[j])
            {
                minn=dis[j];
                now=j;
            }
        }
        sum+=dis[now];
        vis[now]=1;
        connect[now][pre[now]]=connect[pre[now]][now]=1;
        for (int j=1;j<=n;++j)
        {
            if (vis[j])
            {
                maxd[j][now]=maxd[now][j]=max(maxd[j][pre[now]],dis[now]);
            }
            else if (dis[j]>mp[now][j])
            {
                dis[j]=mp[now][j];
                pre[j]=now;
            }
        }
    }
}
int sprim()
{
    int ans=INF;
    for (int i=1;i<=n;++i)
    {
        for (int j=i+1;j<=n;++j)
        {
            if (!connect[i][j]&&mp[i][j]!=INF)
            {
                ans=min(ans,sum+mp[i][j]-maxd[i][j]);
            }
        }
    }
    return ans;
}
int main()
{
    int x,y,w,t;
    scanf("%d",&t);
    while (t--)
    {
        memset(mp,INF,sizeof(mp));
        scanf("%d%d",&n,&m);
        for (int i=1;i<=m;++i)
        {
            scanf("%d%d%d",&x,&y,&w);
            mp[x][y]=w;
            mp[y][x]=w;
        }
        prim();
        int res=sprim();
        if (sum==res) printf("Not Unique!
");
        else printf("%d
",sum);
    }
}

C++バージョン3
Kruskyalアルゴリズム

#include
#include
#include
#define ll long long
#define pb push_back
#define INF 0x3f3f3f3f
#define FI first
#define SE second
#define MP make_pair
#define PI pair
#define lson l,m,rt<<1,ls,rs
#define rson m+1,r,rt<<1|1,ls,rs
#define test printf("here!!!
")
using namespace std;
const int mx=1e4+10;
const int MX=5e3+10;
int n,m;
struct Node
{
    int st;
    int to;
    ll w;
    friend bool operator >1]+1;
    for (int i=1;i<=n;++i)
    {
        head[i]=0,dis[i]=0,vis[i]=0,pre[i]=i,sz[i]=1;
    }
    memset(ma,0,sizeof(ma));
    memset(fa,0,sizeof(fa));
    memset(use,0,sizeof(use));
    dis[0]=-1;
}
int unfd(int x)
{
    int r=x;
    while (r!=pre[r]) r=pre[r];
    int t;
    while (x!=pre[x])
    {
        t=pre[x];
        pre[x]=r;
        x=t;
    }
    return r;
}
int unjoin(int x,int y)
{
    int fx=unfd(x),fy=unfd(y);
    if (fx!=fy)
    {
        if (sz[fx]dis[v])
    {
        int loog=lg[dis[u]-dis[v]];
        maxn=max(ma[u][loog],maxn);
        u=fa[u][loog];
    }
    if (u==v) return maxn;
    for (int i=lg[dis[u]];i>=0;--i)
    {
        if (fa[u][i]!=fa[v][i])
        {
            maxn=max(max(ma[u][i],ma[v][i]),maxn);
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return max(max(ma[u][0],ma[v][0]),maxn);
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d",&n,&m);
        int x,y;
        ll z;
        init();
        for (int i=1;i<=m;++i)
        {
            scanf("%d%d%lld",&vec[i].st,&vec[i].to,&vec[i].w);
        }
        sort(vec+1,vec+m+1);
        kruskal();
        dfs(1,0);
        ll ans=0x3f3f3f3f3f3f3f3f;
        for (int i=1;i<=m;++i)
        {
            if (!use[i])
            {
                ans=min(ans,sum-LCA(vec[i].st,vec[i].to)+vec[i].w);
            }
        }
        if (ans==sum) printf("Not Unique!
");
        else printf("%lld
",sum);
    }
}

C++バージョン4

#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
 
using namespace std;
int n,m;
struct data
{
    int u,v,w;
    bool vis;
} p[20010];
vectorG[110];
int per[110],maxd[110][110];
bool cmp(data a,data b)
{
    return a.w < b.w;
}
int Union_Find(int x)
{
    return x == per[x] ? x: per[x] = Union_Find(per[x]);
}
void kruskal()
{
    sort(p,p+m,cmp);
    for(int i=0; i<=n; i++)//   
    {
        G[i].clear();
        G[i].push_back(i);
        per[i]=i;
    }
    int sum=0,k=0;//sum        
    for(int i=0; isum)
        printf("%d
",sum);
    else
        printf("Not Unique!
");
}
int main()
{
    int T;
    scanf("%d
",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i