这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
最小生成树(MST)讲解请看: [http://www.wutianqi.com/?p=1284](http://www.wutianqi.com/?p=1284) |
题目传送门: http://acm.hdu.edu.cn/showproblem.php?pid=1875 Prim版本: 31MS 372K 1314 B C++ 解答报告:
#include
#include
using namespace std;
const int INF = 10000000;
double arcs[205][205], dis[205];
int x[205], y[205], vis[205];
int nCases, islands;
int x_tmp, y_tmp, rec;
double tmp, _min;
bool flag;
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d", &nCases;);
while(nCases--)
{
scanf("%d", &islands;);
for(int i=0; i1000)
tmp = INF;
arcs[i][j] = arcs[j][i] = tmp;
}
}
for(int i=1; i
Kruskal版本: 187MS 284K 1654 B C++ 解答报告:
#include
#include
#include
using namespace std;
typedef struct Road
{
int c1, c2;
double cost;
}Road;
struct Point
{
int x, y;
};
bool myCompare(const Road &a;, const Road &b;)
{
if(a.cost < b.cost)
return 1;
return 0;
}
Road road[5051];
Point point[101];
int city[101];
int Find(int n)
{
if(city[n] == -1)
return n;
return city[n] = Find(city[n]);
}
bool Merge(int s1, int s2)
{
int r1 = Find(s1);
int r2 = Find(s2);
if(r1 == r2)
return 0;
if(r1 < r2)
city[r2] = r1;
else
city[r1] = r2;
return 1;
}
int main()
{
//freopen("input.txt", "r", stdin);
int n;
int nCases;
scanf("%d", &nCases;);
while(nCases--)
{
scanf("%d", &n;);
for(int i=0; i=10 && Merge(road[i].c1, road[i].c2))// ??????
{
count ++;
sum += road[i].cost;
}
if(count == n-1)
break;
}
if(count == n-1)
printf("%.1lf\n", sum*100);
else
puts("oh!");
}
return 0;
}