http://acm.hdu.edu.cn/showproblem.php?pid=1863
这道浙大的考研上机题题意大致是:给一个带全图,若连图,则输出该图的最小生成树的权值之和,不连通,输出?.
我用Prim算法求解MST,求解然之后判断是否连通,判断连通并没有去重新遍历图一遍。用了一个小技巧。
我的AC代码。
#include<iostream>
#include<stdio.h>
using namespace std;
const int Infinity = 1000000000;
const int Max = 100 + 10;
int g[Max][Max];
int edges, vers;
struct Node
{
int adj;
int closeDist;
bool along;
};
Node Mst[Max];
void Prim()
{
Mst[1].along = true;
for(int i=2; i<=vers; i++)
{
Mst[i].adj = 1;
Mst[i].closeDist = g[1][i];
Mst[i].along = false;
}
int min, pos;
for(int i=1; i<vers; i++)
{
min = Infinity + 1, pos = 0;
for(int j=1; j<=vers; j++)
{
if(!Mst[j].along && min > Mst[j].closeDist)
{
min = Mst[j].closeDist;
pos = j;
}
}
Mst[pos].along = true;
for(int j=1; j<=vers; j++)
{
if(!Mst[j].along && g[j][pos] < Mst[j].closeDist)
{
Mst[j].closeDist = g[j][pos];
Mst[j].adj = pos;
}
}
}
}
int main()
{
int head, tail, cost;
while(scanf("%d%d", &edges, &vers) && edges)
{
for(int i=0; i<Max; i++)
for(int j=0; j<Max; j++) g[i][j] = Infinity;
for(int i=0; i<edges; i++)
{
scanf("%d%d%d", &head, &tail, &cost);
g[head][tail] = g[tail][head] = cost;
}
Prim();
bool connected = true;
int sum = 0;
for(int i=1; i<=vers; i++)
{
if(Mst[i].closeDist == Infinity)
{
connected = false;
break;
}
else sum += Mst[i].closeDist;
}
if(connected) printf("%d\n", sum);
else printf("?\n");
}
system("pause");
return 0;
}