Electrification Plan(最小生成树)

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=50#problem/D

最小生成树模板,注意的是这里有k个发电站,它们不再需要连接其他的发电站,所以任何两个发电站之间的权值是0;

 #include<stdio.h>
#include<string.h>
const int maxn = ;
const int INF = 0x3f3f3f3f;
int map[maxn][maxn],power[maxn];
int n,k; void prim()
{
int dis[maxn],vis[maxn];
int ans = ;
memset(vis,,sizeof(vis));
for(int i = ; i <= n; i++)
dis[i] = map[][i];
vis[] = ; for(int i = ; i <= n-; i++)
{
int min = INF,pos; for(int j = ; j <= n; j++)
{
if(!vis[j] && dis[j] < min)
{
min = dis[j];
pos = j;
}
}
vis[pos] = ;
ans += min;
for(int j =; j <= n; j++)
{
if(!vis[j] && dis[j] > map[pos][j])
dis[j] = map[pos][j];
}
}
printf("%d\n",ans);
} int main()
{
scanf("%d %d",&n,&k); /*for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
{
if(i != j)
map[i][j] = INF;
else map[i][j] = 0;
}*/
memset(power,,sizeof(power));
int x; for(int i = ; i < k; i++)
{
scanf("%d",&x);
power[x] = ;
} for(int i = ; i <= n; i++)
{
for(int j = ; j <= n; j++)
scanf("%d",&map[i][j]);
} for(int i = ; i <= n; i++)
{
for(int j = ; j <= n; j++)
{
if(power[i] && power[j])
map[i][j] = ;
}
}
prim();
return ;
}
上一篇:Arduino IDE 添加DHT11传感器第三方库的方法


下一篇:前端js面试中的常见的算法问题