首页 > 代码库 > timus 1982 Electrification Plan(最小生成树)
timus 1982 Electrification Plan(最小生成树)
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 builda 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.
Output
Output the minimum cost to electrify all the cities.
Sample
| input | output |
|---|---|
4 21 40 2 4 32 0 5 24 5 0 13 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 10000typedef long long ll;using namespace std;const int N=6005;const int M=50000;int power(int a,int b,int c){int ans=1;while(b){if(b%2==1){ans=(ans*a)%c;b--;}b/=2;a=a*a%c;}return ans;}int a[N],w[N][N],vis[N],lowcost[N];int n,m,k;void prim(){ int sum=0;lowcost[1]=-1; for(int i=2;i<=n;i++){ lowcost[i]=w[1][i]; } for(int i=1;i<n;i++){ int minn=inf,k; for(int j=1;j<=n;j++){ if(lowcost[j]!=-1&&lowcost[j]<minn){ k=j;minn=lowcost[j]; } } sum+=minn; lowcost[k]=-1; for(int j=1;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=1;i<=m;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&w[i][j]); for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)w[a[i]][a[j]]=0; prim(); return 0;}
timus 1982 Electrification Plan(最小生成树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。