timus 1982 Electrification Plan(最小生成树)

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 c_ij 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 {c_ij} (0 ≤ c_ij ≤ 10⁵).
It is guaranteed that c_ij = c_ji, c_ij > 0 for i ≠ j, c_ii = 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

【分析】将任意两个带有发电站的城市之间的距离赋为0，然后prim求最小生成树。(这么简单的思路我居然没有想到，还是学长教我的)。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <time.h>

#include <string>

#include <map>

#include <stack>

#include <vector>

#include <set>

#include <queue>

#define inf 10000000

#define mod 10000

typedef long long ll;

using namespace std;

const int N=;

const int M=;

int power(int a,int b,int c){int ans=;while(b){if(b%==){ans=(ans*a)%c;b--;}b/=;a=a*a%c;}return ans;}

int a[N],w[N][N],vis[N],lowcost[N];

int n,m,k;

void prim()

{

    int sum=;lowcost[]=-;

    for(int i=;i<=n;i++){

        lowcost[i]=w[][i];

    }

    for(int i=;i<n;i++){

        int minn=inf,k;

        for(int j=;j<=n;j++){

            if(lowcost[j]!=-&&lowcost[j]<minn){

                k=j;minn=lowcost[j];

            }

        }

        sum+=minn;

        lowcost[k]=-;

        for(int j=;j<=n;j++){

            lowcost[j]=min(lowcost[j],w[k][j]);

        }

    }

    printf("%d\n",sum);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++)scanf("%d",&a[i]);

    for(int i=;i<=n;i++)for(int j=;j<=n;j++)scanf("%d",&w[i][j]);

    for(int i=;i<=m;i++)for(int j=;j<=m;j++)w[a[i]][a[j]]=;

    prim();

    return ;

}

巴特西

timus 1982 Electrification Plan(最小生成树)

Electrification Plan

Input

Output

Sample

最新文章

热门文章