poj1258(Agri-Net)最小生成树

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

28

裸的最小生成树，直接kruskal或者prim算法

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;

struct edge
{
    int u, v, w;
    bool operator < (const edge& b) const
    {
        return w < b.w;
    }
};

edge es[10000];
int V, E;
int f[110];

void init()
{
    for (int i = 0; i < 110; ++i)
        f[i] = i;
}

int Find(int x)
{
    return x == f[x] ? x : (f[x] = Find(f[x]));
}

void join(int x, int y)
{
    int fx = Find(x), fy = Find(y);
    f[fx] = fy;
}

int kruskal()
{
    sort(es, es+E);
    init();
    int res = 0;
    for (int i = 0; i < E; ++i)
    {
        edge e = es[i];
        if (Find(e.u) != Find(e.v))
        {
            join(e.u, e.v);
            res += e.w;
        }
    }
    return res;
}

int main()
{
    while (~scanf("%d", &V))
    {
        E = 0;
        int w;
        for (int i = 0; i < V; ++i)
            for (int j = 0; j < V; ++j)
            {
                scanf("%d", &w);
                if (j > i)
                es[E++] = edge{i, j, w};
            }
        printf("%d\n", kruskal());
    }
    return 0;
}