kuangbin六A：POJ 1251 Jungle Roads（最小生成树模板题）

Description：

模板题没啥好说的

prim：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f;

int Map[30][30];
void init()
{
    for(int i = 0; i < 30; i++)
        for(int j = 0; j < 30; j++)
            Map[i][j] = INF;
}

bool vis[30];
int dis[30];
int prim(int n)
{
    int path_sum = 0;
    memset(vis, false, sizeof(vis));
    vis[0] = true;
    for(int i = 1; i < n; i++)
        dis[i] = Map[0][i];
    for(int i = 1; i < n; i++)
    {
        int path = INF, p = -1;
        for(int j = 0; j < n; j++)
            if(!vis[j] && path > dis[j])
            {
                path = dis[j];
                p = j;
            }
        if(path == INF) return -1;
        path_sum += path;
        vis[p] = true;
        for(int j = 0; j < n; j++)
            if(!vis[j] && dis[j] > Map[p][j])
                dis[j] = Map[p][j];
    }
    return path_sum;
}

int main()
{
    int n;
    while(scanf("%d", &n) && n)
    {
        init();
        char fch, tch;
        int num_e = 0, len;
        for(int i = 0; i < n-1; i++)
        {
            //getchar();//receive last row's \n
            scanf(" %c %d", &fch, &num_e);
            while(num_e--)
            {
                //getchar();//receive the ' ' at the left of char
                scanf(" %c %d", &tch, &len);
                Map[int(fch-'A')][int(tch-'A')] = len;
                Map[int(tch-'A')][int(fch-'A')] = len;
            }
        }
        printf("%d\n", prim(n));
    }
    return 0;
}

kruskal：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f;
const int N = 30;

int edge_num = 0;
struct Edge
{
    int from, to, val;
}edge[N*N*2];

bool cmp(Edge a, Edge b)
{
    return a.val < b.val;
}

void addEdge(int a, int b, int len)
{
    edge[edge_num].from = a;
    edge[edge_num].to = b;
    edge[edge_num++].val = len;
}

int pre[N], Rank[N];
void BC_init(int n)
{
    for(int i = 0; i < n; i++)
        pre[i] = i;
    memset(Rank, 0, sizeof(Rank));
}

int Find(int x)
{
    int r = x;
    while(r != pre[r]) //寻找总前驱
        r = pre[r];
    int i = x, j;
    while(i != r) //路径压缩
    {
        j = pre[i];
        pre[i] = r;
        i = j;
    }
    return r;
}

void Join(int p1, int p2)
{
    int root1 = Find(p1);
    int root2 = Find(p2);
    if(root1 == root2) return;
    if(Rank[root1] < Rank[root2])
        pre[root1] = root2;
    else
    {
        if(Rank[root1] == Rank[root2])
            Rank[root1]++;
        pre[root2] = root1;
    }
}

int kruskal(int n)
{
    BC_init(n);
    int path_sum = 0;
    sort(edge, edge+edge_num, cmp);
    for(int i = 0; i < edge_num; i++)
        if(Find(edge[i].from) != Find(edge[i].to))
        {
            Join(edge[i].from, edge[i].to);
            path_sum += edge[i].val;
        }
    return path_sum;
}

int main()
{
    int n;
    while(scanf("%d", &n) && n)
    {
        edge_num = 0;
        char fch, tch;
        int num_e = 0, len;
        for(int i = 0; i < n-1; i++)
        {
            scanf(" %c %d", &fch, &num_e);
            while(num_e--)
            {
                scanf(" %c %d", &tch, &len);
                int a = int(fch-'A'), b = int(tch-'A');
                addEdge(a, b, len);
                addEdge(b, a, len);
            }
        }
        printf("%d\n", kruskal(n));
    }
    return 0;
}