題目鏈接：http://poj.org/problem?id=1258
裸的最小生成樹求邊權(quán)值，給的是鄰接矩陣，但是鄰接矩陣的kruskal我不會(huì)用，就轉(zhuǎn)換成了邊表然后使用，說(shuō)實(shí)話挺蛋疼的，但是好歹A掉了。。。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 101
int a[N][N];
struct edge
{
int u, v, w;
}e[20010];
int tot, p[N];
void add(int x, int y, int z)
{
tot++;
e[tot].u = x;
e[tot].v = y;
e[tot].w = z;
}
int find(int x)
{
return p[x] != x ? p[x] = find(p[x]) : x;
}
int cmp(edge a, edge b)
{
return a.w < b.w;
}
int main()
{
int r1, r2, ans, n;
while (scanf("%d", &n) != EOF)
{
tot = 0; memset(e, 0, sizeof(e));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
scanf("%d", &a[i][j]);
if (a[i][j] != 0) add(i, j, a[i][j]);
}
for (int i = 1; i <= n; i++) p[i] = i;
ans = 0;
sort(e + 1, e + tot + 1, cmp);
for (int i = 1; i <= tot; i++)
{
r1 = find(e[i].u); r2 = find(e[i].v);
if (r1 != r2)
{
p[r2] = r1;
ans += e[i].w;
}
}
printf("%d\n", ans);
}
return 0;
}