如何求解Uva 6437电力厂问题中的裸最小生成树？

本文共计488个文字，预计阅读时间需要2分钟。

题目：在一个无向图中（最多100个点），每条边都有其耗费...有些点是发电站...现在要找到所有的点都能到达的最少发电站...所需的最小耗费...

解题：先将发电站的所有点放入一个集合中。然后将这些点两两相连，找到所有相连的点构成的集合。接着，重复上述步骤，直到所有点都被包含在集合中。最后，从集合中找到耗费最小的点即可。

题意:

一个无向图中(至多100个点),..每条边有其费用...有些点是发电站..现在要求所有的点都可以达到至少一个发电站..所需的最小费用..

题解:

先就把发电站的点放到一个集合中..然后裸的kruskal了...

Program:

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cmath>
#define MAXN 205
using namespace std;
struct node
{
int u,v,d;
}edge[MAXN*MAXN];
int father[MAXN];
int getfather(int x)
{
if (father[x]==x) return x;
return father[x]=getfather(father[x]);
}
bool cmp(node a,node b)
{
return a.d<b.d;
}
int main()
{
int C,cases,N,K,M,i,u,v,f,ans;
scanf("%d",&C);
for (cases=1;cases<=C;cases++)
{
scanf("%d%d%d",&N,&M,&K);
for (i=1;i<=N;i++) father[i]=i;
scanf("%d",&f);
for (i=2;i<=K;i++) scanf("%d",&u),father[u]=f;
for (i=1;i<=M;i++)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].d);
sort(edge+1,edge+1+M,cmp);
ans=0;
for (i=1;i<=M;i++)
{
u=edge[i].u,v=edge[i].v;
if (getfather(u)==getfather(v)) continue;
ans+=edge[i].d;
father[father[u]]=father[v];
}
printf("Case #%d: %d\n",cases,ans);
}
return 0;
}