HDU.1233 还是畅通工程（Prim）
题意分析
首先给出n，代表村庄的个数然后出n*(n-1)/2个信息，每个信息包括村庄的起点，终点，距离，要求求出最小生成树的权值之和。注意村庄的编号从1开始即可直接跑prim
代码总览
#include <bits/stdc++.h>
#define nmax 105
#define inf 1e8+7
using namespace std;
int mp[nmax][nmax];
int n;
int totaldis =
0;
void prim()
{
int lowcost[nmax];
int path[nmax];
for(
int j =
1;j<=n;++j){
lowcost[j] = mp[
1][j];
path[j] =
1;
}
path[
1] =
0;
int nowmin,nowminid;
for(
int i =
2 ;i<=n;++i){
nowmin = inf;
nowminid =
0;
for(
int j =
2;j<=n;++j){
if(nowmin > lowcost[j] && lowcost[j] !=
0){
nowmin = lowcost[j];
nowminid = j;
}
}
totaldis += nowmin;
lowcost[nowminid] =
0;
for(
int j =
2;j<=n;++j){
if(mp[nowminid][j] < lowcost[j]){
lowcost[j] = mp[nowminid][j];
path[j] = nowminid;
}
}
}
}
int main()
{
while(
scanf(
"%d",&n) != EOF && n){
int sta,end,dis;
totaldis =
0;
for(
int i =
1; i<=n;++i)
for(
int j =
1;j<=n;++j)
mp[i][j] = inf;
for(
int i =
1; i<=n*(n-
1)/
2 ;++i){
scanf(
"%d %d %d",&sta,&end,&dis);
mp[sta][end] = mp[end][sta] = dis;
}
prim();
printf(
"%d\n",totaldis);
}
return 0;
}
