「Bzoj 2200」「Usaco2011 Jan」道路和航线(最短路+DAG图拓扑序转移)

发表于 | 分类于 | | + s

BZOJ 2200
题意：无向图中求$S$出发到每个点的最短路。并且有一些单向边，如果有一条单向边可以从$A_i$到$B_i$，那么保证不可能通过一些双向边和单向边从$B_i$回到$A_i$

显然最短路模板，但是有负权图并且卡 SPFA。
所以我们利用

如果有一条单向边可以从$A_i$到$B_i$，那么保证不可能通过一些双向边和单向边从$B_i$回到$A_i$

发现这些有向边将无向图分成了几个联通块，即不加入这些有向边，原图为几个连通块。
所以我们将联通块缩点，然后就成了 DAG 上的最短路，然后拓扑序来求即可。

具体实现看代码。

知识点：
1、负权图转移要注意判 != INF

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 25000 + 5;
    const LL INF = 4223372036854775808ll;

    struct edge {
        int u, v, w;
    }ed[200000 + 5];
    struct data {
        int u;
        LL dis;
        bool operator < (const data &rhs) const {return dis > rhs.dis;}
    };

    int n, m, p, s, f[MAXN], en, ino[MAXN], vis[MAXN]; // f[节点编号], ino[联通块代表编号], vis[节点编号]
    vector<int > G[MAXN], whw[MAXN]; // G[节点编号][ith]=边编号 
    LL dis[MAXN]; //dis[节点编号]
    queue<int > qq; // qq<联通块代表编号>

    int find(int x) {return x == f[x] ? x : f[x] = find(f[x]);} // find(节点编号)
    void ins(int x, int y, int v) {ed[++en] = (edge){x, y, v}, G[x].push_back(en);} // ins(节点编号, 节点编号, 值) 

    priority_queue<data > q; // q<信息>[联通块代表编号]

    void dij(int nx) {
        for (int i = 0; i < (int)whw[nx].size(); ++i) q.push((data){whw[nx][i], dis[whw[nx][i]]});
        while (!q.empty()) {
            data p = q.top(); q.pop();
            if (vis[p.u]) continue ; vis[p.u] = 1;
            for (int i = 0; i < (int)G[p.u].size(); ++i) {
                edge &e = ed[G[p.u][i]];
                if (dis[e.v] > dis[p.u] + e.w && dis[p.u] != INF) { // 负权图注意判 != INF
                    dis[e.v] = dis[p.u] + e.w;
                    if (find(e.v) == nx) q.push((data){e.v, dis[e.v]});
                }
            }
        }
        for (int i = 0; i < (int)whw[nx].size(); ++i) { // 把边删完 
            int u = whw[nx][i];
            for (int j = 0; j < (int)G[u].size(); ++j) {
                int v = ed[G[u][j]].v;
                if (find(v) == nx) continue ;
                --ino[find(v)];
                if (ino[find(v)] == 0) qq.push(find(v));
            }
        }
    }

    void clean() {
        ms(vis, 0), ms(ino, 0), en = 0;
    }
    int solve() {
        clean();
        scanf("%d%d%d%d", &n, &m, &p, &s);
        for (int i = 0; i <= n; ++i) f[i] = i;
        for (int x, y, v, i = 1; i <= m; ++i) {
            scanf("%d%d%d", &x, &y, &v);
            ins(x, y, v), ins(y, x, v);
            int hx = find(x), hy = find(y);
            if (hx != hy) f[hx] = hy;
        }
        for (int x, y, v, i = 1; i <= p; ++i) {
            scanf("%d%d%d", &x, &y, &v), ins(x, y, v);
        }
        for (int i = 2 * m + 1; i <= 2 * m + p; ++i) {
            int hx = find(ed[i].u), hy = find(ed[i].v);
            if (hx != hy) ++ino[hy];
        }

        for (int i = 1; i <= n; ++i) whw[find(i)].push_back(i);

        for (int i = 1; i <= n; ++i) dis[i] = INF;
        dis[s] = 0ll;

        for (int i = 1; i <= n; ++i) if (find(i) == i && ino[i] == 0) qq.push(i);

        while (!qq.empty()) {
            int p = qq.front(); qq.pop();
            dij(p);
        }
        for (int i = 1; i <= n; ++i) if (dis[i] == INF) printf("NO PATH\n"); else printf("%lld\n", dis[i]);
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
//21:17  -  :34  -  20:48   -  20:48   -  20:56
//Start  -  Finish -  Static  -  Sample  -   AC 
/*
4 0 4 3
1 3 5
1 4 4
3 4 6
4 2 6
*/
------ 本文结束 ------