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[105]; int o; int pra[105]; int sum = 0; struct node { int u, v, w; }a[10200]; 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 = 0; int i; sort(a + 1, a + o, cmp); for (i = 1; i <= o - 1;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 = 1; i <= k; i++) { cin >> di[i];//发电站 } o = 1; for (i = 1; i <= k; i++) { for (j = 1; j <= k; j++) {//把发电站之间的w设为0就可以了 a[o].u = di[i]; a[o].v = di[j]; a[o++].w = 0; } } for (i = 1; i <= n; i++) { pra[i] = i; for (j = 1; j <= n; j++) { a[o].u = i; a[o].v = j; cin >> a[o++].w; } } kruskal(); cout << sum << endl; } }