首页 > 代码库 > URAL 1982. Electrification Plan（并查集）
URAL 1982. Electrification Plan（并查集）
题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1982
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 incij 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.
Input
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 × ntable of integers {cij} (0 ≤ cij ≤
105). It is guaranteed that , cij >
0 for i ≠ j, cii = 0.
Output
Output the minimum cost to electrify all the cities.
Sample
| input | output |
|---|---|
4 2 1 4 0 2 4 3 2 0 5 2 4 5 0 1 3 2 1 0 |
3 |
题意：
给出一些建有电站的城市，求每一个城市都通电的最小花费。
代码例如以下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 10017;
int father[maxn];
int n;
int flag;
struct node
{
int x, y;
int c;
} cc[maxn];
int find(int x)
{
return x==father[x] ? x:father[x]=find(father[x]);
}
void init()
{
for(int i = 1; i <= n; i++)
{
father[i] = i;
}
}
void Union(int x, int y)
{
flag = 0;
int f1 = find(x);
int f2 = find(y);
if(f1 != f2)
{
flag = 1;
father[f2] = f1;
}
}
bool cmp(node a, node b)
{
return a.c < b.c;
}
int main()
{
int k;
while(~scanf("%d%d",&n,&k))
{
init();
int m;
for(int i = 1; i <= k; i++)
{
scanf("%d",&m);
father[m] = -1;
}
int l = 0;
int cost;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
scanf("%d",&cost);
cc[l].x = i, cc[l].y = j;
cc[l].c = cost;
l++;
}
}
int num = n*n;
sort(cc,cc+num,cmp);
int ans = 0;
for(int i = 1; i <= num; i++)
{
Union(cc[i].x, cc[i].y);
if(flag)
ans+=cc[i].c;
}
printf("%d\n",ans);
}
return 0;
}URAL 1982. Electrification Plan（并查集）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。