URAL 1982. Electrification Plan

Author: 2015-08-18

ACM

, , , , ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1982

1982. Electrification Plan

Time limit: 0.5 second
Memory limit: 64 MB
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 cij 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 × n table of integers {cij} (0 ≤ cij ≤ 105). It is guaranteed thatcij = cji, 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
Problem Author: Mikhail Rubinchik
Problem Source: Open Ural FU Championship 2013

2. 思路

给出n个城市两两之间建设输电线的费用，和k个建有发电站的城市，求将所有城市通上电（与建有发电站的城市间建设输电线）的最小费用。

求无向带权图的最小生成树。题目输入直接是图的邻接矩阵，直接使用很方便。开始给出的k个建有发电站的城市，看做已经相互连通，在此基础上求最小生成树。

下面的代码使用Prim算法求最小生成树。

3. 代码

#include <stdio.h>

#define MAX_CITY_NUM 101
#define MAX_COST 100001

typedef int CostMap[MAX_CITY_NUM][MAX_CITY_NUM];

void solveE3d_ElectrificationPlan();
void inputCostMap(CostMap costMap, int n);

int main() {
    solveE3d_ElectrificationPlan();
    return 0;
}

int powerStations[MAX_CITY_NUM];
CostMap costMap;
bool hasPower[MAX_CITY_NUM];
void solveE3d_ElectrificationPlan() {
    int n, k;
    scanf("%d %d", &n, &k);

    for (int i = 0; i < k; ++i) {
        scanf("%d", &powerStations[i]);
        hasPower[powerStations[i]] = true;
    }

    inputCostMap(costMap, n);

    int minCost = MAX_COST, minCostId, totalCost = 0;
    while (k < n) {
        minCost = MAX_COST;
        for (int i = 1; i <= n; ++i) {
            if (!hasPower[i]) {
                for (int j = 0; j < k; ++j) {
                    if (costMap[i][powerStations[j]] < minCost) {
                        minCost = costMap[i][powerStations[j]];
                        minCostId = i;
                    }
                }
            }
        }
        totalCost += minCost;
        hasPower[minCostId] = true;
        powerStations[k++] = minCostId;
    }

    printf("%d\n", totalCost);
}

void inputCostMap(CostMap costMap, int n) {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &costMap[i][j]);
        }
    }
}