算法拾遗[3]——图论算法

发表于 | 分类于

夏令营复习算法, 感到自己对之前学过的算法略有生疏, 写篇流水账, 权当复习.

  • 并查集
  • Dijkstra 算法
  • Floyd 算法
  • Kruskal 算法

并查集

处理连通关系的一种手段.

查询所属连通分支

1
2
3
4
5
6
7
8
9
// fa[i] 表示i 所属的连通分支的代表元
// rnk[j] 表示j 号连通分支的结点个数, 注意这里的j 必须是所取的代表元(根结点)
// 使用前注意fa[] 的初始化, rnk[] 初始为1.
int fa[maxn], rnk[maxn];
int Find(int x)
{
    if (fa[x] == -1) return x;
    else return fa[x] = Find(fa[x]);
}

合并操作

1
2
3
4
5
6
7
8
9
10
void Union(int x, int y)
{
    int t1 = Find(x);
    int t2 = Find(y);
    if(t1 != t2)
    {
        fa[t1] = t2;
        rnk[t2] += rnk[t1];
    }
}

Dijkstra 算法

单源最短路, 适用于权值非负的图.

实现代码

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
// g 需要初始化, 下标从0 开始.
const int maxn = 1005;
const int inf = 0x3f3f3f3f;

int pre[maxn], d[maxn];
int g[maxn][maxn];
bool vis[maxn];

void Dijkstra(int g[][maxn], int d[], int n, int s)
{
    for (int i = 0; i < n; i++)
    {
        pre[i] = -1;
        vis[i] = false;
        d[i] = inf;
    }
    d[s] = 0;
    for (int j = 0; j < n; j++)
    {
        int k = -1, Min = inf;
        for (int i = 0; i < n; i++)
            if (!vis[i] && d[i] < Min)
            {
                Min = d[i];
                k = i;
            }
        if (k == -1) break;
        vis[k] = true;
        for (int i = 0; i < n; i++)
            if (!vis[i] && d[k] + g[k][i] < d[i])
            {
                d[i] = d[k] + g[k][i];
                pre[i] = k;
            }
    }
}

HDU 2544: 最短路

Problem Description

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。 输入保证至少存在1条商店到赛场的路线。

Output

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

Sample Input

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

Sample Output

3
2

大致思路

注意题目中下标从 1 开始.

AC代码

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;
const int inf = 0x3f3f3f3f;

int pre[maxn], d[maxn];
int g[maxn][maxn];
bool vis[maxn];

void Dijkstra(int g[][maxn], int d[], int n, int s)
{
    for (int i = 0; i < n; i++)
    {
        pre[i] = -1;
        vis[i] = false;
        d[i] = inf;
    }
    d[s] = 0;
    for (int j = 0; j < n; j++)
    {
        int k = -1, Min = inf;
        for (int i = 0; i < n; i++)
            if (!vis[i] && d[i] < Min)
            {
                Min = d[i];
                k = i;
            }
        if (k == -1) break;
        vis[k] = true;
        for (int i = 0; i < n; i++)
            if (!vis[i] && d[k] + g[k][i] < d[i])
            {
                d[i] = d[k] + g[k][i];
                pre[i] = k;
            }
    }
}

int main()
{
    int n, m;
    while (cin >> n >> m)
    {
        if (n == 0 && m == 0) break;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                g[i][j] = (i == j) ? 0 : inf;
        while (m--)
        {
            int u, v, w;
            cin >> u >> v >> w;
            g[u - 1][v - 1] = g[v - 1][u - 1] = w;
        }
        Dijkstra(g, d, n, 0);
        cout << d[n - 1] << endl;
    }

    return 0;
}

Floyd 算法

我所知道的唯一的全源最短路. 复杂度略高, 约 \(O(n^3)\). 可以视为动态规划. 简单好写.

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
// 初始化仍然是i == j时d[i][j]为0, 其余为inf.
// 注意下标从0 开始, 以及k-> i-> j 的顺序.
// 想压行可以把最后的if 写成min.
int d[maxn][maxn];

void floyd(int n)
{
    for (int k = 0; k < n; k++) // 一定要注意第一层是k
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
}

HDU 2544: 最短路

Problem Description

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。 输入保证至少存在1条商店到赛场的路线。

Output

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

Sample Input

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

Sample Output

3
2

大致思路

还是这道裸题…除了注意题目中下标从 1 开始我都不知道还有什么可说的.

AC代码

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;
const int inf = 0x3f3f3f3f;

int d[maxn][maxn];

void floyd(int n)
{
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
}

int main()
{
    int n, m;
    while (cin >> n >> m)
    {
        if (n == 0 && m == 0) break;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (i == j) d[i][j] = 0;
                else d[i][j] = inf;
        while (m--)
        {
            int a, b, c;
            cin >> a >> b >> c;
            d[a - 1][b - 1] = d[b - 1][a - 1] = c;
        }
        floyd(n);
        cout << d[0][n - 1] << endl;
    }

    return 0;
}

Kruskal 算法

所有边排序, 逐条加边, 用并查集判连通, 求最小生成树.

实现代码

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
// 并查集初始化为-1, 不需要在main函数里单独初始化
// tol 需要在main里单独初始化为0
const int maxn = 1005;

struct Edge
{
    int u, v, w;
    Edge(){}
    Edge(int a, int b, int c): u(a), v(b), w(c){}
} e[maxn];

int tol; // 存总边数

void addedge(int u, int v, int w)
{
    e[tol++] = Edge(u, v, w);
}

bool cmp(Edge a, Edge b) // 按权值排序
{
    return a.w < b.w;
}

int fa[maxn]; // 并查集

int Find(int x)
{
    if(fa[x] == -1) return x;
    else return fa[x] = Find(fa[x]);
}

int Kruskal(int n)
{
    memset(fa, -1, sizeof(fa));
    sort(e, e + tol, cmp);
    int cnt(0), res(0);
    for (int i = 0; i < tol; i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        int t1 = Find(u);
        int t2 = Find(v);
        if (t1 != t2)
        {
            fa[t1] = t2;
            res += w;
            cnt++;
        }
        if (cnt == n - 1) break;
    }
    if (cnt < n - 1) return -1; // 不连通
    else return res; // 连通返回最小生成树权值
}

HDU 1863: 畅通工程

Problem Description

省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当N为0时，全部输入结束，相应的结果不要输出。

Output

对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。

Sample Input

3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100

Sample Output

3
?

大致思路

裸题, 没什么好说的, 一定要注意 tol 的初始化.

AC代码

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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1005;

struct Edge
{
    int u, v, w;
    Edge() {}
    Edge(int a, int b, int c): u(a), v(b), w(c) {}
} e[maxn]; // 一般情况下完全可以考虑用 vector 存边
int tol;

void addedge(int u, int v, int w)
{
    e[tol++] = Edge(u, v, w);
}

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

int fa[maxn];

int Find(int x)
{
    while (fa[x] != x)
        x = fa[x];
    return x;
}

int Kruskal(int n)
{
    for(int i = 0; i < n; i++) // 需要注意下标是从0还是1开始
        fa[i] = i;
    sort(e, e + tol, cmp);
    int cnt(0), res(0);
    for (int i = 0; i < tol; i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        int t1 = Find(u);
        int t2 = Find(v);
        if (t1 != t2)
        {
            fa[t1] = t2;
            res += w;
            cnt++;
        }
        if(cnt == n - 1) break;
    }
    if (cnt < n - 1) return -1;
    else return res;
}

int main()
{
    int n, m;
    while (cin >> m >> n)
    {
        if (m == 0) break;
        tol = 0; // 初始化!!!
        while (m--)
        {
            int u, v, w;
            cin >> u >> v >> w;
            addedge(u, v, w);
        }
        int ans = Kruskal(n);
        if (ans == -1) printf("?\n");
        else printf("%d\n", ans);
    }

    return 0;
}