算法作业题

算法作业记录

担心很多东西学过就忘了，就写 blog 加深印象和后期回顾

Work 1

1.求最小生成树的Prim算法

题目描述：
请编写程序，实现在带权的无向图中求最小生成树的 Prim 算法。 注意：当多个待收录顶点到当前点集的距离等长时，按编号升序进行收录。

输入格式：
输入首先在第一行给出两个正整数，依次为当前要创建的图的顶点数 n（≤100）和边数 m。 随后 m 行，每行给出一条无向边两端点的编号、权重。顶点编号从 0 开始，权重（≤100）为整数。同行数字均以一个空格分隔。

输出格式：
参考样例。 首先在一行中输出 total weight = x，其中 x 为最小生成树中所有边的总权重。如果最小生成树不存在，则 x 为 −1。 随后在一行中按顶点编号升序输出每个顶点在最小生成树中的父结点的编号。为输出简单起见，每个数字后有一个空格。 注意：此处默认顶点 0 为最小生成树的根结点，其父结点编号规定为 −1。算法初始化时，所有顶点（除了根结点）的父结点编号默认为 0。

输入样例 1：

6 9
0 1 1
0 2 3
1 2 6
1 3 2
2 3 7
2 4 5
2 5 4
3 5 8
4 5 1

输出样例 1：

total weight = 11
-1 0 0 1 5 2 

输入样例 2：

7 9
0 1 1
0 2 3
1 2 6
1 3 2
2 3 7
2 4 5
2 5 4
3 5 8
4 5 1

输出样例 2：

total weight = -1
-1 0 0 1 5 2 0 

这题就是 prim算法 的模板题，需要注意的是图一定要用邻接表储存，空间: $O(n + m)$；邻接矩阵存储，空间: $O(n \times m)$，这个内存是会爆的

解题代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;

vector<int> res;
int prim(int n, const vector<vector<pii>>& adj) {
    vector<int> dist(n, INF);
    vector<int> parent(n, 0);
    vector<bool> visited(n, false);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[0] = 0;
    parent[0] = -1;
    pq.push({0, 0});

    int cost = 0, cnt = 0;
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (visited[u]) continue;

        visited[u] = true;
        cost += d;
        cnt++;

        for (auto& edge: adj[u]) {
            auto [v, w] = edge;
            if (!visited[v] && w < dist[v]) {
                dist[v] = w;
                parent[v] = u;
                pq.push({w, v});
            }
        }
    }

    res = move(parent);
    return (cnt == n) ? cost : -1;
}

int main()
{
    int n, m;
    cin >> n >> m;

    vector<vector<pii>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); // 无向图，别忘了加边
    }

    cout << "total weight = " << prim(n, adj) << endl;
    for (auto num : res) cout << num << " ";
    cout << endl;

    return 0;
}

2.最短路的交点

题目描述：
给定有向加权图 G，和 4 个顶点 u, v, s, t。假设图 G 中所有边的权值都非负。设计一个算法来判定“从 u 到 v 的最短路径”和“从 s 到 t 的最短路径”是否存在一个交点 w。也即，顶点 w 是 u 到 v 的最短路径上的一个顶点，同时也是 s 到 t 的最短路径上的一个顶点。 注意：最短路径包含两个端点；一对顶点间的最短路径可能不止一条，求交点时必须将所有最短路径考虑在内。

输入格式：
输入第 1 行给出 6 个正整数，依次为：n（≤1000，图中顶点数）、m（≤3000，图中边数）、题面中描述的 4 个顶点 u, v, s, t 的编号。这里假设顶点从 1 到 n 编号，并且 u, v, s, t 的编号均不相同。 随后 m 行，每行给出一条有向边的起点编号、终点编号、非负权重（≤100）。题目保证每条边都不会重复给出，同行数字间以空格分隔。

输出格式：
在一行中，按编号递增的顺序输出所有交点。数字间以 1 个空格分隔，行首尾不得有多余空格。如果交点不存在，则在一行中输出 No Intersection。

输入样例 1：

6 7 1 2 3 4
1 2 3
1 5 1
3 5 1
5 6 1
5 4 2
6 4 1
6 2 1

输出样例 1：

5 6

输入样例 2：

4 4 1 2 3 4
1 2 1
3 4 1
1 4 1
3 2 1

输出样例 2：

No Intersection

解释：

• 本题主要考察 dijkstra算法及其性质 的应用
• dijkstra算法 ：求该点到图中其它点的的最短路径长度， 二叉堆优化实现时间复杂度: $O((V+E)\log V)\approx O(E\log V)$，其中 V, E 分别是顶点数、边数
• dist_u[v]表示u 到 v 的最短路径距离，记 w 为其它点，若 dist_u[w] + dist_w[v] = dist_u[v]，则表明 w 在 u->v 的最短路径上
  • 对于 dist_u[w] 和 dist_u[v] 只需要对 u 跑一次 dijkstra 即可得到
  • 对于 dist_w[v]，我们不可能对所有点跑 dijkstra 得到所有点的 dist_x[v]，其中 x 代表任意一点，因为时间复杂度为 $O(V\cdot E\cdot \log V)$，效率太低
• 于是我们不求每个点到 v 的最短路径长度，而是求 v 到各个点的最短路径长度，于是我们构建反图，即代码(main函数)中 rev
  • 因为这是有向图，所以原图若有 u->v，则反图应有 v->u，因为两者的路径长度是相同的，均为 w
  • 所以所有点到 v 的最短路径长度可以转为反图中 v 到各点的的最短路径长度(即从n次dijkstra减少到1次)
• 得到 u, v, s, t 点的 dijkstra 结果数组后即可遍历各点判断交点

注意：

• INF 一定不能参与判断逻辑，否则会被卡一个1分的测试点
• 对应代码块：(同时也是核心判断逻辑)

if (dist_u[i] != INF && dist_v[i] != INF &&
    dist_s[i] != INF && dist_t[i] != INF &&
    dist_u[i] + dist_v[i] == dist_u[v] && 
    dist_s[i] + dist_t[i] == dist_s[t]) 
            
    res.push_back(i);

解题代码：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;

vector<int> dijkstra(int n, int start, const vector<vector<pii>>& adj) {
    vector<int> dist(n + 1, INF);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto [v, w]: adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

int main()
{
    int n, m, u, v, s, t;
    cin >> n >> m >> u >> v >> s >> t;

    vector<vector<pii>> adj(n + 1), rev(n + 1);
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w;

        adj[x].push_back({y, w});
        rev[y].push_back({x, w});
    }

    auto dist_u = dijkstra(n, u, adj);
    auto dist_v = dijkstra(n, v, rev);
    auto dist_s = dijkstra(n, s, adj);
    auto dist_t = dijkstra(n, t, rev);

    vector<int> res;

    for (int i = 1; i <= n; i++) {
        if (dist_u[i] != INF && dist_v[i] != INF &&
            dist_s[i] != INF && dist_t[i] != INF &&
            dist_u[i] + dist_v[i] == dist_u[v] && 
            dist_s[i] + dist_t[i] == dist_s[t]) 
            
            res.push_back(i);
    }

    if (res.empty()) {
        cout << "No Intersection";
    } else {
        for (int i = 0; i < res.size(); i++) {
            if (i == res.size() - 1) cout << res[i];
            else cout << res[i] << " ";
        }
    }
    cout << endl;
    
    return 0;
}

3.强连通分量

题目描述：
本题请你编写程序，输出给定有向图中的各个强连通分量，并统计强连通分量的个数。

输入格式： 输入首先在第一行给出 2 个整数，依次为有向图的顶点数 n（0<n≤15）和边数 m。 随后 m 行，每行给出一条有向边的起点和终点编号。编号从 0 开始，其间以 1 个空格分隔。

输出格式： 按照 { v1 v2 ... vk } 的格式，每行输出一个强连通分量中的所有顶点 v1~vk 的编号。最后一行输出强连通分量的个数。

输入样例：

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

输出样例：

{ 0 1 3 }
{ 2 }
2

注意： 强连通分量的输出顺序是不唯一的，以任何顺序输出都可以，有特殊裁判程序判断输出的正确性。例如下列输出也是正确的。

{ 2 }
{ 1 3 0 }
2

解释：

• 此题主要考察 tarjan算法 应用
• tarjan: 用一次 dfs 找出所有强连通分量
  • 主要维护 dfn数组, low数组, st栈
  • 主要讨论新增边为树边和回边的情况

具体原理学习 Click Here

解题代码：

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int N = 16;
vector<int> dfn(N, 0), low(N, 0);
vector<bool> inStack(N, false);
stack<int> st;
vector<vector<int>> adj(N);

int timer = 0, scc_cnt = 0;

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    st.push(u);
    inStack[u] = true;

    for (auto v : adj[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if (inStack[v]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        scc_cnt++;

        cout << "{ ";
        while (true) {
            int top = st.top();
            st.pop();
            inStack[top] = false;

            cout << top;
            if (top == u) break;
            cout << " ";
        }
        cout << " }" << endl;
    }
}

int main()
{
    int n, m;
    cin >> n >> m;


    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    for (int i = 0; i < n; i++) if (!dfn[i]) tarjan(i);
    cout << scc_cnt << endl;

    return 0;
}

后面的题有点小难，还在努力中...