POJ.1287 Networking (Prim)
题意分析
可能有重边，注意选择最小的边。编号依旧从1开始。直接跑prim即可。
代码总览
#include <cstdio>
#include <cstring>
#define nmax 105
#define inf 1e8+7
using namespace std;
int mp[nmax][nmax];
bool isfind =
true;
int n,m;
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;
}
}
if(nowmin == inf){
isfind =
false;
return;
}
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){
scanf(
"%d",&m);
int sta,end,dis;
totaldis =
0;
isfind =
true;
for(
int i =
1; i<=n;++i)
for(
int j =
1;j<=n;++j)
mp[i][j] = inf;
for(
int i =
1; i<=m ;++i){
scanf(
"%d %d %d",&sta,&end,&dis);
if(mp[sta][end] != inf){
int temp = mp[sta][end];
if(dis < temp)
mp[sta][end] = mp[end][sta] = dis;
}
else{
mp[sta][end] = mp[end][sta] = dis;
}
}
prim();
if(isfind ==
false) totaldis =
0;
printf(
"%d\n",totaldis);
}
return 0;
}
