洛谷 P1967 [NOIP 2013 提高组] 货车运输

// P1967 货车运输 —— 正解：**最大生成树 ＋ 倍增维护路径最小边权**
//
// ★ 这道题是[第 34 章（最小生成树）](/ch/34-mst/)和[第 51 章第 13 步](/ch/51-lca/)的合体，
//   而它立在一句需要证明的话上：
//
//   > **在最大生成树上，x 到 y 那条路径的最小边权，就是原图上所有 x→y 路径里
//   > 「最小边权」能取到的最大值。**
//
//   一句话的道理：把边按权值**从大到小**加（Kruskal 求最大生成树），
//   x 和 y 第一次连通的那一刻，用到的最后一条边就是答案 ——
//   再小的边加进来也改不了「已经连通」这件事，而更早（更大）的边不足以让它们连通。
//   ⇒ 解析页第 ③ 步用一条**完全无关的路**（每询问跑一次「最大瓶颈路」）把它验了一遍。
//
// ⚠⚠ 三处题面写着的坑：
//   ① **图不保证连通** ⇒ 最大生成**森林**，两点不在同一棵树里就输出 −1；
//   ② **`0 ≤ z`** ⇒ 答案可以是 **0**，而 0 和 −1 是两件事（别拿 0 当「不通」的标志）；
//   ③ **两座城市之间可能有多条道路**（重边）—— Kruskal 天然不怕，可暴力那边要小心。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int MAXM = 50005;
const int LOG = 15;                       // 2^14 = 16384 > 10⁴
const int INF = 0x3f3f3f3f;

struct Edge { int u, v, w; };
Edge es[MAXM];
int fa[MAXN];

int head_[MAXN], nxt_[MAXN * 2], to_[MAXN * 2], wt_[MAXN * 2], ecnt;   // ★ 只存生成森林的边 ⇒ 至多 2(n−1) 条
int up[MAXN][LOG];                        // 祖先
int mn[MAXN][LOG];                        // ★ 同一张表，换个东西记：到 2^k 级祖先那一段的**最小边权**
int dep[MAXN], comp[MAXN];                // comp = 属于哪一棵树（森林）
int n, m, q;

int find_(int x) { while (fa[x] != x) x = fa[x] = fa[fa[x]]; return x; }
inline void addEdge(int u, int v, int w) { to_[++ecnt] = v; wt_[ecnt] = w; nxt_[ecnt] = head_[u]; head_[u] = ecnt; }

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 0; i < m; i++)
        if (scanf("%d %d %d", &es[i].u, &es[i].v, &es[i].w) != 3) return 0;

    /* ① 最大生成森林：按权值**从大到小**排（⚠ 不是从小到大） */
    sort(es, es + m, [](const Edge& a, const Edge& b) { return a.w > b.w; });
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 0; i < m; i++) {
        int a = find_(es[i].u), b = find_(es[i].v);
        if (a == b) continue;             // 已经连通（重边、成环的边都在这儿被丢掉）
        fa[a] = b;
        addEdge(es[i].u, es[i].v, es[i].w);
        addEdge(es[i].v, es[i].u, es[i].w);
    }

    /* ② 每棵树各 BFS 一趟（⚠ ① 是森林，不是一棵树） */
    {
        vector<char> vis(n + 1, 0);
        vector<int> que;
        que.reserve(n);
        for (int r = 1; r <= n; r++) {
            if (vis[r]) continue;
            vis[r] = 1; dep[r] = 0; comp[r] = r;
            up[r][0] = r; mn[r][0] = INF;  // 根往上没有边 ⇒ 那一段的最小边权是「无穷大」
            que.clear(); que.push_back(r);
            for (size_t i = 0; i < que.size(); i++) {
                int u = que[i];
                for (int e = head_[u]; e; e = nxt_[e]) {
                    int v = to_[e];
                    if (vis[v]) continue;
                    vis[v] = 1; dep[v] = dep[u] + 1; comp[v] = r;
                    up[v][0] = u; mn[v][0] = wt_[e];
                    que.push_back(v);
                }
            }
        }
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++) {
            up[v][k] = up[up[v][k - 1]][k - 1];
            mn[v][k] = min(mn[v][k - 1], mn[up[v][k - 1]][k - 1]);   // ★ 两段拼起来取 min
        }

    if (scanf("%d", &q) != 1) return 0;
    while (q--) {
        int x, y;
        if (scanf("%d %d", &x, &y) != 2) return 0;
        if (comp[x] != comp[y]) { printf("-1\n"); continue; }        // ⚠ ① 不连通
        int res = INF;
        if (dep[x] < dep[y]) swap(x, y);
        int d = dep[x] - dep[y];
        for (int k = 0; k < LOG; k++)
            if ((d >> k) & 1) { res = min(res, mn[x][k]); x = up[x][k]; }
        if (x != y) {
            for (int k = LOG - 1; k >= 0; k--)
                if (up[x][k] != up[y][k]) {
                    res = min(res, min(mn[x][k], mn[y][k]));
                    x = up[x][k]; y = up[y][k];
                }
            res = min(res, min(mn[x][0], mn[y][0]));                 // ⚠ 最后各再上一步
        }
        printf("%d\n", res);
    }
    return 0;
}

// P1967 的两笔账：这份数据长什么样，以及两条路各做多少次基本动作（机器无关）
//
// 用法：./p1967Count <csv|table> < 一份输入

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int MAXM = 50005;
const int LOG = 15;
const int INF = 0x3f3f3f3f;

struct Edge { int u, v, w; };
static Edge es[MAXM];
static int fa[MAXN];
static int head_[MAXN], nxt_[MAXN * 2], to_[MAXN * 2], wt_[MAXN * 2], ecnt;
static int up[MAXN][LOG], mn[MAXN][LOG], dep[MAXN], comp[MAXN];
static int gh[MAXN], gn[MAXM * 2], gt[MAXM * 2], gw[MAXM * 2], gc;
static int n, m, q;

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

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 0; i < m; i++) {
        if (scanf("%d %d %d", &es[i].u, &es[i].v, &es[i].w) != 3) return 0;
        gt[++gc] = es[i].v; gw[gc] = es[i].w; gn[gc] = gh[es[i].u]; gh[es[i].u] = gc;
        gt[++gc] = es[i].u; gw[gc] = es[i].w; gn[gc] = gh[es[i].v]; gh[es[i].v] = gc;
    }
    sort(es, es + m, [](const Edge& a, const Edge& b) { return a.w > b.w; });
    for (int i = 1; i <= n; i++) fa[i] = i;
    int used = 0;
    for (int i = 0; i < m; i++) {
        int a = find_(es[i].u), b = find_(es[i].v);
        if (a == b) continue;
        fa[a] = b; used++;
        to_[++ecnt] = es[i].v; wt_[ecnt] = es[i].w; nxt_[ecnt] = head_[es[i].u]; head_[es[i].u] = ecnt;
        to_[++ecnt] = es[i].u; wt_[ecnt] = es[i].w; nxt_[ecnt] = head_[es[i].v]; head_[es[i].v] = ecnt;
    }
    int comps = n - used, maxDep = 0;
    {
        vector<char> vis(n + 1, 0);
        vector<int> que; que.reserve(n);
        for (int r = 1; r <= n; r++) {
            if (vis[r]) continue;
            vis[r] = 1; dep[r] = 0; comp[r] = r; up[r][0] = r; mn[r][0] = INF;
            que.clear(); que.push_back(r);
            for (size_t i = 0; i < que.size(); i++) {
                int u = que[i];
                for (int e = head_[u]; e; e = nxt_[e]) {
                    int v = to_[e];
                    if (vis[v]) continue;
                    vis[v] = 1; dep[v] = dep[u] + 1; comp[v] = r;
                    up[v][0] = u; mn[v][0] = wt_[e]; que.push_back(v);
                }
            }
        }
        for (int i = 1; i <= n; i++) maxDep = max(maxDep, dep[i]);
    }
    for (int k = 1; k < LOG; k++)
        for (int v = 1; v <= n; v++) { up[v][k] = up[up[v][k - 1]][k - 1]; mn[v][k] = min(mn[v][k - 1], mn[up[v][k - 1]][k - 1]); }

    if (scanf("%d", &q) != 1) return 0;
    long long jumps = 0, relax = 0;
    int neg = 0, zero = 0;
    vector<int> best(n + 1);
    for (int t = 0; t < q; t++) {
        int x, y;
        if (scanf("%d %d", &x, &y) != 2) return 0;
        /* ① 倍增：数「跳了多少次」 */
        int ans;
        if (comp[x] != comp[y]) ans = -1;
        else {
            int a = x, b = y, res = INF;
            if (dep[a] < dep[b]) swap(a, b);
            int d = dep[a] - dep[b];
            for (int k = 0; k < LOG; k++) if ((d >> k) & 1) { res = min(res, mn[a][k]); a = up[a][k]; jumps++; }
            if (a != b) {
                for (int k = LOG - 1; k >= 0; k--) if (up[a][k] != up[b][k]) { res = min(res, min(mn[a][k], mn[b][k])); a = up[a][k]; b = up[b][k]; jumps += 2; }
                res = min(res, min(mn[a][0], mn[b][0]));
            }
            ans = res;
        }
        if (ans < 0) neg++; else if (ans == 0) zero++;
        /* ② 暴力：数「松弛了多少条边」 */
        for (int i = 1; i <= n; i++) best[i] = -1;
        best[x] = INT_MAX;
        priority_queue<pair<int, int> > pq;
        pq.push(make_pair(best[x], x));
        while (!pq.empty()) {
            pair<int, int> tt = pq.top(); pq.pop();
            int u = tt.second;
            if (tt.first != best[u]) continue;
            if (u == y) break;
            for (int e = gh[u]; e; e = gn[e]) {
                relax++;
                int v = gt[e], cand = min(best[u], gw[e]);
                if (cand > best[v]) { best[v] = cand; pq.push(make_pair(cand, v)); }
            }
        }
    }

    vector<pair<string, string> > out;
    out.push_back(make_pair("n", to_string(n)));
    out.push_back(make_pair("m", to_string(m)));
    out.push_back(make_pair("q", to_string(q)));
    out.push_back(make_pair("comps", to_string(comps)));
    out.push_back(make_pair("maxdep", to_string(maxDep)));
    out.push_back(make_pair("ans_neg", to_string(neg)));
    out.push_back(make_pair("ans_zero", to_string(zero)));
    out.push_back(make_pair("jumps", to_string(jumps)));
    out.push_back(make_pair("relax", to_string(relax)));
    char buf[64]; snprintf(buf, sizeof(buf), "%.0f", relax / (double)max(1LL, jumps));
    out.push_back(make_pair("ratio", string(buf)));

    if (mode == "csv") for (size_t i = 0; i < out.size(); i++) printf("%s,%s\n", out[i].first.c_str(), out[i].second.c_str());
    else for (size_t i = 0; i < out.size(); i++) printf("  %-10s %s\n", out[i].first.c_str(), out[i].second.c_str());
    return 0;
}