题意: 一个无向图中(至多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;
}