交付导航加联网一起验收

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

这是这条路线的最终作品。其余函数都已写好，补全 has_neg_cycle、same_set、without 三个函数，一次验完五条：① 0 到 4 的最短总长是 6，路径是 0-1-3-4；② 负权图上 Dijkstra 给 5、Bellman-Ford 给 3；③ 负权图没有负环，负环图有；④ Kruskal 和 Prim 的总长都是 7，边集完全相同；⑤ 拆掉最贵的边 MST 还是 7，拆掉最便宜的涨到 15。五条全过输出 验收通过，否则输出 验收失败。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 第四步拆掉一条边试试十万个点该用哪种写法 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;
const ll INF = 1000000000;                       // 走不到的点记这个值，输出时写成 -1
using Graph = vector<vector<pair<int, int>>>;    // g[u] 里放 (邻居 v, 边权 w)

// 七个点的无向图（和 Python 版同一组数据）：0-1:2 0-2:1 1-3:3 2-4:9 3-4:1 5-6:7
const vector<vector<int>> E7 = {{0, 1, 2}, {0, 2, 1}, {1, 3, 3}, {2, 4, 9}, {3, 4, 1}, {5, 6, 7}};
// 主连通块五个点、五条边（求最小生成树用）
const vector<vector<int>> E5 = {{0, 1, 2}, {0, 2, 1}, {1, 3, 3}, {2, 4, 9}, {3, 4, 1}};
// 有向负权反例：0→1:4 0→2:5 2→1:-3 1→3:1
const Graph NEG = {{{1, 4}, {2, 5}}, {{3, 1}}, {{1, -3}}, {}};
// 同一张图，只把 2→1 那条边改成 +3
const Graph POS = {{{1, 4}, {2, 5}}, {{3, 1}}, {{1, 3}}, {}};
// 有负环：0→1:1 1→2:-1 2→1:-1
const Graph CYC = {{{1, 1}}, {{2, -1}}, {{1, -1}}};

Graph build(int n, const vector<vector<int>>& edges) {
    // 无向图：每条边 {a, b, w} 两个方向都加；邻接表按邻居编号排好
    Graph g(n);
    for (const auto& e : edges) {
        g[e[0]].push_back({e[1], e[2]});
        g[e[1]].push_back({e[0], e[2]});
    }
    for (auto& adj : g) sort(adj.begin(), adj.end());
    return g;
}

vector<ll> dijkstra(const Graph& g, int s) {
    vector<ll> d(g.size(), INF);
    vector<bool> done(g.size(), false);
    // 小根堆：greater 让距离小的先出（不写就是大根堆）
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    d[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [du, u] = pq.top();
        pq.pop();
        if (done[u]) continue;
        done[u] = true;
        for (auto [v, w] : g[u]) {
            if (du + w < d[v]) {
                d[v] = du + w;
                pq.push({d[v], v});
            }
        }
    }
    return d;
}

vector<int> back_track(const vector<int>& par, int t) {
    // 从终点顺着 par 一路回到起点（起点的 par 是 -1），再翻过来
    vector<int> path;
    for (int x = t; x != -1; x = par[x]) path.push_back(x);
    reverse(path.begin(), path.end());
    return path;
}

vector<int> dij_path(const Graph& g, int s, int t) {
    vector<ll> d(g.size(), INF);
    vector<int> par(g.size(), -1);
    vector<bool> done(g.size(), false);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    d[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [du, u] = pq.top();
        pq.pop();
        if (done[u]) continue;
        done[u] = true;
        for (auto [v, w] : g[u]) {
            if (du + w < d[v]) {
                d[v] = du + w;
                par[v] = u;
                pq.push({d[v], v});
            }
        }
    }
    return back_track(par, t);
}

string path_str(const vector<int>& p) {
    string s;
    for (size_t i = 0; i < p.size(); i++) s += (i ? "-" : "") + to_string(p[i]);
    return s;
}

vector<ll> bellman(const Graph& g, int s) {
    int n = g.size();
    vector<ll> d(n, INF);
    d[s] = 0;
    for (int round = 0; round < n - 1; round++) {
        for (int u = 0; u < n; u++) {
            if (d[u] == INF) continue;
            for (auto [v, w] : g[u]) {
                if (d[u] + w < d[v]) d[v] = d[u] + w;
            }
        }
    }
    return d;
}

bool has_neg_cycle(const Graph& g, int s) {
    // TODO: 先照常跑 bellman；再多看一轮，只要还有一条边能松弛成功，就返回 true
    return false;
}

vector<int> make_set(int n) {
    vector<int> p(n);
    for (int i = 0; i < n; i++) p[i] = i;
    return p;
}

int find_root(vector<int>& p, int x) {
    while (p[x] != x) {
        p[x] = p[p[x]];      // 路径压缩：挂到爷爷上
        x = p[x];
    }
    return x;
}

bool unite(vector<int>& p, int a, int b) {
    // 两端已在同一块里就返回 false（这条边会成环）
    int ra = find_root(p, a), rb = find_root(p, b);
    if (ra == rb) return false;
    p[ra] = rb;
    return true;
}

struct MST {
    ll total;
    vector<pair<int, int>> picked;
};

MST kruskal(int n, vector<vector<int>> edges) {
    // 按 (权重, 两端编号) 从小到大排，union 成功才要这条边
    sort(edges.begin(), edges.end(), [](const vector<int>& x, const vector<int>& y) {
        if (x[2] != y[2]) return x[2] < y[2];
        if (x[0] != y[0]) return x[0] < y[0];
        return x[1] < y[1];
    });
    vector<int> p = make_set(n);
    MST r{0, {}};
    for (const auto& e : edges) {
        if (unite(p, e[0], e[1])) {
            r.total += e[2];
            r.picked.push_back({e[0], e[1]});
        }
    }
    return r;
}

MST prim(int n, const vector<vector<int>>& edges, int s) {
    vector<vector<pair<int, int>>> ad(n);       // ad[u] 里放 (w, x)
    for (const auto& e : edges) {
        ad[e[0]].push_back({e[2], e[1]});
        ad[e[1]].push_back({e[2], e[0]});
    }
    vector<bool> seen(n, false);
    seen[s] = true;
    // 堆里放 (权重, 树里那端, 树外那端)，权重小的先出
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    for (auto [w, v] : ad[s]) pq.push({w, s, v});
    MST r{0, {}};
    int cnt = 1;
    while (!pq.empty() && cnt < n) {
        auto [w, u, v] = pq.top();
        pq.pop();
        if (seen[v]) continue;
        seen[v] = true;
        cnt++;
        r.total += w;
        r.picked.push_back({u, v});
        for (auto [w2, x] : ad[v]) {
            if (!seen[x]) pq.push({w2, v, x});
        }
    }
    return r;
}

bool same_set(const vector<pair<int, int>>& a, const vector<pair<int, int>>& b) {
    // TODO: 两组边各自规范成 (小编号, 大编号) 放进 set，再比较两个 set
    return false;
}

vector<vector<int>> without(const vector<vector<int>>& edges, int a, int b) {
    // TODO: 返回去掉 a-b（两个方向都算）之后的边
    (void)a; (void)b;
    return edges;
}

int main() {
    Graph g = build(7, E7);
    vector<bool> checks;
    checks.push_back(dijkstra(g, 0)[4] == 6 && path_str(dij_path(g, 0, 4)) == "0-1-3-4");
    checks.push_back(dijkstra(NEG, 0)[3] == 5 && bellman(NEG, 0)[3] == 3);
    checks.push_back(!has_neg_cycle(NEG, 0) && has_neg_cycle(CYC, 0));
    MST k = kruskal(5, E5), p = prim(5, E5, 0);
    checks.push_back(k.total == 7 && p.total == 7 && same_set(k.picked, p.picked));
    checks.push_back(kruskal(5, without(E5, 2, 4)).total == 7 && kruskal(5, without(E5, 0, 2)).total == 15);
    bool ok = true;
    for (bool c : checks) ok = ok && c;
    cout << (ok ? "验收通过" : "验收失败") << endl;
}

本次输入：

输出：

👩‍🏫

AI

💬 题目评论

交付导航加联网一起验收

更多题目

全部评论