链接：http://poj.org/problem?id=1258
Description
Input
Output
Sample Input
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0
Sample Output
28
解题思路： 最简单的最小生成树的题目；MST-Kruscal
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <iomanip>
#include <cassert>
#include <algorithm>
#define LC(x) (x<<1)
#define RC(x) (LC(x)+1)
#define PI (acos(-1))
#define EPS 1e-8
#define MAXN 111111
#define MAXM 222222
#define LL long long
#define ULL unsigned long long
#define INF 0x7fffffff
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;
struct edge {
int v, u, cost;
}e[111*111];
bool cmp_e(const edge &a, const edge &b)
{
return a.cost < b.cost;
}
int ecnt, fa[111], n, v;
void addedge(int u, int v, int cost)
{
e[++ ecnt].v = v, e[ecnt].u = u, e[ecnt].cost = cost;
}
int getf(int x)
{
return fa[x] == x ? x : fa[x] = getf(fa[x]);
}
int kruscal()
{
int sum = 0;
for(int i = 1; i <= n; i ++) fa[i] = i;
sort(e + 1, e + 1 + ecnt, cmp_e);
for(int i = 1; i <= ecnt; i ++) {
int u = e[i].u, v = e[i].v;
u = getf(u), v = getf(v);
if(u == v) continue;
sum += e[i].cost;
fa[u] = v;
}
return sum;
}
int main()
{
while(scanf("%d", &n) == 1) {
ecnt = 0;
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= n; j ++) {
scanf("%d", &v);
if(v != 0) addedge(i, j, v);
}
}
printf("%d\n", kruscal());
}
return 0;
}
POJ 1258 Agri-Net （MST-Kruscal）,布布扣,bubuko.com
POJ 1258 Agri-Net （MST-Kruscal）
原文：http://blog.csdn.net/keshacookie/article/details/23115853