题目链接：?space=1&num=1982
Some country hasncities. The government has decided to electrify all these cities. At first, power stations inkdifferent cities were built. The other cities should be connected with the power stations via power lines. For any citiesi,jit is possible to build a power line between them incijroubles. 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 integersnandk(1 ≤k≤n≤ 100). The second line containskdifferent integers that are the numbers of the cities with power stations. The nextnlines contain ann×ntable of integers {cij} (0 ≤cij≤ 105). It is guaranteed thatcij=cji,cij> 0 fori≠j,cii= 0.
Output
Output the minimum cost to electrify all the cities.
Sample
inputoutput
4 21 40 2 4 32 0 5 24 5 0 13 2 1 03
题意：
给出一些建有电站的城市，，求每个城市都通电的最小花费；
代码如下：
#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;}
一个人，一条路，人在途中，心随景动，从起点，
