POJ 1287 Networking

Description

n个点，m条边（两点间的路可能不止一条），求最小生成树

传送门

Code of Kruskal

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 105;///点的上限,因为RE我开大了

int n, m, ans;
int pre[N];

int cnt;
struct edge
{
    int there, here, w;
}a[N * N];

bool cmp(edge a, edge b)
{
    return a.w < b.w;
}

void init()
{
    ans = 0;
    for(int i = 0; i <= n; ++i)
        pre[i] = i;
}

int found(int x)
{
    if(x != pre[x])
        pre[x] = found(pre[x]);
    return pre[x];
}

int unite(edge t)
{
    int x = found(t.there);
    int y = found(t.here);
    if(x != y)
    {
        pre[y] = x;
        return t.w;
    }
    return 0;
}

int main()
{
    while(~scanf("%d", &n))
    {
        if(n == 0)
            break;
        scanf("%d", &m);
        init();
        int b, c, d;
        for(int i = 0; i < m; ++i)
            scanf("%d%d%d", &a[i].there, &a[i].here, &a[i].w);
        sort(a, a + m, cmp);
        for(int i = 0; i < m; ++i)
            ans += unite(a[i]);
        cout << ans << '\n';
    }
    return 0;
}

Code of Prim

注意每两点间的路在记录时就选最短的

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;///mmin以及mp的初始化
const int N = 105;

int n, m, ans;

///三个基本数组
bool vis[N];///是否入树
int mp[N][N];///邻接矩阵存图
int low[N];///low[i]已成图所有点到点i最小距离

///n-1次循环的三部分:①找点②连入③更新
void prim()
{
    ans = 0;
    memset(vis, 0, sizeof(vis));

    int mmin, pos = 1;
    vis[1] = 1;
    for(int i = 1; i <= n; ++i)
        low[i] = mp[pos][i];

    int cnt = n;
    while(--cnt)///n个点，连接 n - 1 条路
    {
        mmin = INF;
        for(int i = 1; i <= n; ++i)
            if(!vis[i] && low[i] < mmin)///找未连入树的且离树最近的
            {
                mmin = low[i];///这段最小距离的权值
                pos = i;///位置（哪个点）
            }

        ///if(mmin == INF)有时连不成树
        vis[pos] = 1;
        ans += mmin;

        for(int i = 1; i <= n; ++i)
            if(!vis[i] && low[i] > mp[pos][i])
                low[i] = mp[pos][i];
    }
    cout << ans << '\n';
}

int main()
{
    while(~scanf("%d", &n) && n)
    {
        scanf("%d", &m);
        memset(mp, INF, sizeof(mp));
        int b, c, d;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &b, &c, &d);
            if(mp[b][c] == INF)
                mp[b][c] = mp[c][b] = d;
            else
            {
                if(d < mp[b][c])
                    mp[b][c] = mp[c][b] = d;
            }
        }
        prim();
    }
    return 0;
}