題目大意：判斷一個圖的最小生成樹是否有唯一的構成。
只要求出這個圖的次小生成樹，比較和最小生成樹的大小即可。先用Kruskal求出MST，刪去MST中一條邊（即不允許這條邊被再次選擇），再求刪去此邊時的Sec-MST，最終求出最小的那個Sec-MST。
以下是我的代碼：
在我的程序中稱“次小生成樹”為MMST，而不是Sec-MST的簡寫SMST，感覺我的這種叫法也挺不錯！
#include<stdio.h>
const long maxn=107,INF=20000007;
typedef struct
{
long u,v,w;
}edge;
long n,m,mst,mmst,f[maxn];
edge a[maxn*maxn];
bool mst_edge[maxn*maxn],can[maxn*maxn];
long min(long a,long b)
{
return (a<b?a:b);
}
void Qsort(long begin,long end)
{
long i=begin,j=end,mid=a[(begin+end)/2].w;
edge t;
do{
while(a[i].w<mid) i++;
while(a[j].w>mid) j--;
if(i<=j)
{
t=a[i];a[i]=a[j];a[j]=t;
i++;j--;
}
}while(i<=j);
if(begin<j) Qsort(begin,j);
if(i<end) Qsort(i,end);
}
void Make_set()
{
for(long i=1;i<=n;i++) f[i]=i;
}
long Find(long x)
{
if(f[x]==x) return x;
f[x]=Find(f[x]);
return f[x];
}
void Union(long x,long y)
{
f[Find(x)]=Find(y);
}
long MST()
{
long i,j,re=0;
Make_set();
for(i=1,j=0;i<=m&&j<n-1;i++)
if(Find(a[i].u)!=Find(a[i].v))
{
Union(a[i].u,a[i].v);
re+=a[i].w;
mst_edge[i]=true;
j++;
}
return re;
}
long MMST()
{
long i,j,re=0;
Make_set();
for(i=1,j=0;i<=m&&j<n-1;i++)
if(can[i]&&Find(a[i].u)!=Find(a[i].v))
{
Union(a[i].u,a[i].v);
re+=a[i].w;
j++;
}
if(j>=n-1)
return re;
else return INF;
}
int main()
{
long test;
scanf("%ld",&test);
while(test--)
{
scanf("%ld%ld",&n,&m);
for(long i=1;i<=m;i++)
scanf("%ld%ld%ld",&a[i].u,&a[i].v,&a[i].w);
// Input
for(long i=1;i<=m;i++)
{
mst_edge[i]=false;
can[i]=true;
}
Qsort(1,m);
// Init
mst=MST();
// Calculate MST
mmst=INF;
for(long i=1;i<=m;i++)
if(mst_edge[i])
{
can[i]=false;
mmst=min(mmst,MMST());
can[i]=true;
}
// Calculate MMST
if(mmst<=mst)
printf("Not Unique!\n");
else printf("%ld\n",mst);
}
return 0;
}
posted on 2010-02-10 19:16
lee1r 閱讀(401)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論