Electrification Plan
时间限制: 1 Sec 内存限制: 128 MB
提交: 31 解决: 13
[提交][状态][讨论版]
题目描述
Some country has n cities. The government has decided to electrify all these cities. At first, power stations in k different cities were built. The other cities should be connected with the power stations via power lines. For any cities i, j it is possible to build a power line between them in c[i][j] roubles. The country is in crisis after a civil war, so the government decided to build only a few power lines. Of course from every city there must be a path along the lines to some city with a power station. Find the minimum possible cost to build all necessary power lines.
输入
多组测试数据。
The first line contains integers n and k (1 ≤ k ≤ n ≤ 100). The second line contains k different integers that are the numbers of the cities with power stations. The next n lines contain an n × n table of integers c[i][j] (0 ≤ c[i][j] ≤ 10^5). It is guaranteed that c[i][j] = c[j][i], c[i][j] > 0 for i ≠ j, c[i][i] = 0.
输出
Output the minimum cost to electrify all the cities.
样例输入
4 2
1 4
0 2 4 3
2 0 5 2
4 5 0 1
3 2 1 0
样例输出
3 输入的时候很巧妙，要把发电站相互之间的权值设为0
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#define inf 0x3f3f3f3f;
using namespace std;
int n, k;
int di[];
int o;
int pra[];
int sum = ;
struct node
{
int u, v, w;
}a[];
bool cmp(node a, node b)
{
return a.w < b.w;
}
int find(int x)
{
if (pra[x] == x) return x;
else return pra[x] = find(pra[x]);
}
bool same(int x,int y)
{
return find(x) == find(y);
}
void unite(int xx,int yy)
{
int x = find(xx);
int y = find(yy);
if (x == y) return;
else pra[x] = y;
}
void kruskal()//套模版
{
sum = ;
int i;
sort(a + , a + o, cmp);
for (i = ; i <= o - ;i++)
{
node x = a[i];
if (same(a[i].u, a[i].v)) continue;
else
{
sum = sum + a[i].w;
unite(a[i].u, a[i].v);
}
}
}
int main()
{
while (cin >> n >> k)
{
int i, j;
for (i = ; i <= k; i++)
{
cin >> di[i];//发电站
}
o = ;
for (i = ; i <= k; i++)
{
for (j = ; j <= k; j++)
{//把发电站之间的w设为0就可以了
a[o].u = di[i];
a[o].v = di[j];
a[o++].w = ;
}
}
for (i = ; i <= n; i++)
{
pra[i] = i;
for (j = ; j <= n; j++)
{
a[o].u = i;
a[o].v = j;
cin >> a[o++].w;
}
}
kruskal();
cout << sum << endl;
}
}