「USACO 2011 Jan. Gold」道路和航线

题目概述

LOJ #10081. 「一本通 3.2 练习 7」道路和航线 原题来自：USACO 2011 Jan. Gold

Farmer John 正在一个新的销售区域对他的牛奶销售方案进行调查。他想把牛奶送到 $T$ 个城镇 ，编号为 $1$ 到 $T$。这些城镇之间通过 $R$ 条道路（编号为 $1$ 到 $R$）和 $P$ 条航线（编号为 $1$ 到 $P$）连接。每条道路 $i$ 或者航线 $i$ 连接城镇 $A_i$ 到 $B_i$，花费为 $C_i$。

对于道路，$0 \le C_i \le 10^4$，然而航线的花费很神奇，花费 $C_i$ 可能是负数。道路是双向的，可以从 $A_i$ 到 $B_i$，也可以从 $B_i$ 到 $A_i$，花费都是 $C_i$。然而航线与之不同，只可以从 $A_i$ 到 $B_i$。

事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策保证：如果有一条航线可以从 $A_i$ 到 $B_i$，那么保证不可能通过一些道路和航线从 $B_i$ 回到 $A_i$。由于 FJ 的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。他想找到从发送中心城镇 $S$ 把奶牛送到每个城镇的最便宜的方案，或者知道这是不可能的。

如果去掉航线可以发现原图变成了许多连通块

若把一个连通块看成一个节点,则发现连通块和航线组成 DAG

考虑 Topo sort 结合 Dijkstra

称连通块和航线组成的图为 $G$，连通块 $A$ 内部节点和道路的图为 $g_A$

假设 $s$ 所在的连通块为 $S$，对所有在 $G$ 中可从 $S$ 到达的连通块进行拓扑排序（否则算 deg 的时候会算多），一边拓扑一边 Dijkstra

大致是这个样子

q <- Topo_Queue;
while(q not empty):
    clr = q.front(); q.pop();
    
    heap <- Dijkstra_Priority_Queue;
    for (u 为 clr 节点)
        if (dis[u] != INF) heap.push(dis[u], u);
    
    while(heap not empty):
        u = heap.top(); heap.pop();
        for 从 u 出发道路:
            // 普通 Dijkstra 写法，略
        for 从 u 出发的航线(u, v, w):
            A 为 v 所在的连通块;
            if (A 不可从 S 出发到达) continue;
            deg[A]--;
            if (deg[A] == 0) q.push(A);
            dis[v] = min(dis[v], dis[u] + w)

然后代码稍微长了一些

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;

const int N = 25030, inf = 0x3f3f3f3f;

std::vector<pii> g[N];
std::vector<pii> ng[N];
std::vector<int> gg[N];
std::vector<int> block[N];
int color[N], cnt = 0, deg[N], able[N], dis[N], vis[N];

void dfs(int u) {
    block[color[u]].push_back(u);
    for (auto i : g[u]) {
        int v = i.first;
        if (!color[v]) color[v] = color[u], dfs(v);
    }
}

void dfs_gg(int u) {
    able[u] = 1;
    for (auto v : gg[u]) {
        if (!able[v]) dfs_gg(v);
    }
}

int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    std::memset(dis, 0x3f, sizeof(dis));
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int n, r, p, s;
    cin >> n >> r >> p >> s;
    rep(i, 1, r) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back(pii(v, w));
        g[v].push_back(pii(u, w));
    }
    rep(i, 1, n) if (!color[i]) color[i] = ++cnt, dfs(i);  // 连通块划分

    rep(i, 1, p) {
        int u, v, w;
        cin >> u >> v >> w;
        ng[u].push_back(pii(v, w));
        gg[color[u]].push_back(color[v]);
    }
    int ss = color[s];
    dfs_gg(ss);
    // cerr << "connectable divided" << endl;
    rep(u, 1, cnt) {
        if (!able[u]) continue;
        for (auto v : gg[u]) deg[v]++;
    }
    // cerr << "degree calced" << endl;

    dis[s] = 0;
    std::queue<int> q;
    q.push(ss);
    std::priority_queue<pii, std::vector<pii>, std::greater<pii>> heap;
    while (q.size()) {
        int block_id = q.front();
        q.pop();

        for (auto i : block[block_id])
            if (dis[i] < inf) heap.push(pii(dis[i], i));

        while (heap.size()) {
            int u = heap.top().second;
            heap.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (auto i : g[u]) {
                int v = i.first, w = i.second;
                if (dis[v] > dis[u] + w)
                    dis[v] = dis[u] + w, heap.push(pii(dis[v], v));
            }
            for (auto i : ng[u]) {
                int v = i.first, w = i.second;
                if (!able[color[v]]) continue;
                deg[color[v]]--;
                if (deg[color[v]] == 0) q.push(color[v]);
                dis[v] = std::min(dis[v], dis[u] + w);
            }
        }
    }

    rep(i, 1, n) {
        if (dis[i] == inf)
            cout << "NO PATH" << endl;
        else
            cout << dis[i] << endl;
    }
    return 0;
}