poj 1679 The Unique MST （最小生成树是不是唯一 ）

www.MyException.Cn  网友分享于：2013-11-21  浏览：7次
poj 1679 The Unique MST （最小生成树是否唯一 ）

（1）图中每条边，扫描其他边，如果存在权值相同的边，则对其边标记

（2）用kruskal或prim算法求最小生成树的权值

（3）得到最小生成树，如果该最小生成树不包含标记的边，则最小生成树唯一，如果包含了标记的边，则依次去掉标记的边，再求最小生成树，如果求得的最小生成树与原最小生成树的权值相同，则最小生成树不唯一

code:

```#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 105
#define INF 0x7fffffff

using namespace std;

struct node
{
int u, v, w;
int equal;
int used;
int del;
}edge[maxn*maxn];

int parent[maxn];
int n, m;
bool first;

bool cmp( const node &a, const node &b)
{
return a.w < b.w;
}

void UFset( )
{
for(int i = 0; i <= n; i++)
parent[i] = -1;
}

int Find( int x )
{
int s ;
for( s = x; parent[s] >= 0; s = parent[s] );
while(s != x )
{
int temp = parent[x];
parent[x] = s;
x = temp;
}
return s;
}

void Union( int R1, int R2 )
{
int r1 = Find(R1);
int r2 = Find(R2);
int temp = parent[r1] + parent[r2];
if(parent[r1] > parent[r2])
{
parent[r1] = r2;
parent[r2] = temp;
}
else
{
parent[r2] = r1;
parent[r1] = temp;
}
}

int kruskal( )
{
UFset( );
int i, j;
int u, v;
int sumweight = 0, num = 0;
for( i = 0; i <m; i++ )
{
if(edge[i].del == 1 ) continue;

u = edge[i].u; v = edge[i].v;
if( Find(u) != Find(v) )
{
sumweight += edge[i].w;
num++;
Union( u, v );
if( first ) edge[i].used = 1;
}
if( num >= n-1 ) break;
}
return sumweight;
}

int main( )
{
int T, u, v, w, j, i;
scanf("%d",&T);
while( T-- )
{
memset(edge, 0, sizeof(edge) );
scanf("%d%d", &n, &m);
for( i = 0; i < m; i++ )
{
scanf("%d%d%d", &u, &v, &w);
edge[i].u = u;
edge[i].v = v;
edge[i].w = w;
}
for(i = 0; i < m; i++ )
{
for( j = 0; j < m; j++ )
{
if( i == j ) continue;
if( edge[i].w == edge[j].w )
edge[j].equal = 1;
}
}
sort(edge, edge + m, cmp);
first = true;
int ans1 = kruskal( );
int ans2;
first = false;
for( i = 0; i < m; i++ )
{
if(edge[i].used && edge[i].equal )
{
edge[i].del = 1;
ans2 = kruskal( );
if(ans1 == ans2 )
{
printf("Not Unique!\n");
break;
}
edge[i].del = 0;
}
}
if( i >= m )
printf("%d\n", ans1);
}
return 0;
}```