Electrification Plan
Time limit: 0.5 second
Memory limit: 64 MB
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.
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 that cij = cji, cij > 0 for i ≠ j, cii = 0.
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 that cij = cji, cij > 0 for i ≠ j, cii = 0.
Output
Output the minimum cost to electrify all the cities.
Sample
| input | output |
|---|---|
4 2 |
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 ;
}