题目大意：判断一个图的最小生成树是否有唯一的构成。
只要求出这个图的次小生成树，比较和最小生成树的大小即可。先用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 阅读(390)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论