POJ 1251 Jungle roads

Description

左侧图显示当前所有使用中的道路，以及现在每月的维护费用。当然，村庄之间必需有一些公路能够相通，即使路线并不像以前一样短。怎样才使每月的花费最小，并且所维持的道路，将连接所有村庄。

Kruskal

并查集 + sort(edge, edge + cnt, cmp) = Kruskal

结构体存边：遍历每条边，unite每条边的两点

Code of Kruskal

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

int n;///n个点
int ans;
int pre[N];

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

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

void init()
{
    cnt = 0;
    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()
{
///    cout << int('A') << '\n';    65
///    cout << 'A' - 64 << '\n';    1
    while(~scanf("%d", &n) && n)
    {
//        getchar();
        init();
        for(int i = 1; i < n; ++i)
        {
            char now, nxt;
            int num, w;
//            scanf("%c%d", &now, &num);
//            getchar();
            cin >> now >> num;
            while(num--)
            {
//                scanf("%c%d", &nxt, &w);
//                getchar();
                cin >> nxt >> w;
                a[cnt].there = now - 65;
                a[cnt].here = nxt - 65;
                a[cnt++].w = w;
            }
        }
        sort(a, a + cnt, cmp);
        for(int i = 0; i < cnt; ++i)///遍历所有边
            ans += unite(a[i]);
        cout << ans << '\n';
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

对于这个题，用scanf输入总会RE，非法内存访问？cin一次过

Prim

查找部分类似Dijkstra

邻接矩阵存边：遍历每个点，依次连接

注意图是双向的！

邻接矩阵存边: 注定遍历“点”（某些算法所必需）

结构体存边: 注定遍历“边”（高效）

Code of Prim

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

int n;///点的个数
bool vis[30];
int mp[30][30], low[30];///low[i]表示已成图所有点到点i的最小权值

void prim()
{
    int ans = 0;
    memset(vis, 0, sizeof(vis));

    int 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次,一次不能多
    {
        int mmin = INF;
        for(int i = 1; i <= n; ++i)///类dijkstra查找
            if(vis[i] == 0 && 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] == 0 && low[i] > mp[pos][i])
                low[i] = mp[pos][i];
        }
    }
    cout << ans << '\n';
}

int main()
{
    while(~scanf("%d", &n) && n)
    {
        memset(mp, INF, sizeof(mp));
        for(int i = 1; i < n; ++i)
        {
            char now, nxt;
            int num, w;
            cin >> now >> num;
            while(num--)
            {
                cin >> nxt >> w;
                mp[now - 64][nxt - 64] = w;///点为1~n
                mp[nxt - 64][now - 64] = w;///点为1~n
            }
        }
        prim();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66