藍橋杯練習題-《道路和航路》解題報告

藍橋杯練習題-《道路和航路》解題報告

題目連結：http://lx.lanqiao.org/problem.page?gpid=T22

題目描述如下：

農夫約翰正在針對一個新區域的牛奶配送合同進行研究。他打算分發牛奶到T個城鎮（标号為1..T），這些城鎮通過R條标号為（1..R）的道路和P條标号為（1..P）的航路相連。

每一條公路i或者航路i表示成連接配接城鎮Ai（1<=A_i<=T）和Bi（1<=Bi<=T）代價為Ci。每一條公路，Ci的範圍為0<=Ci<=10,000；由于奇怪的營運政策，每一條航路的Ci可能為負的，也就是-10,000<=Ci<=10,000。

每一條公路都是雙向的，正向和反向的花費是一樣的，都是非負的。

每一條航路都根據輸入的Ai和Bi進行從Ai->Bi的單向通行。實際上，如果現在有一條航路是從Ai到Bi的話，那麼意味着肯定沒有通行方案從Bi回到Ai。

農夫約翰想把他那優良的牛奶從配送中心送到各個城鎮，當然希望代價越小越好，你可以幫助他嘛？配送中心位于城鎮S中（1<=S<=T）。

輸入格式

輸入的第一行包含四個用空格隔開的整數T，R，P，S。

接下來R行，描述公路資訊，每行包含三個整數，分别表示Ai，Bi和Ci。

接下來P行，描述航路資訊，每行包含三個整數，分别表示Ai，Bi和Ci。

輸出格式

輸出T行，分别表示從城鎮S到每個城市的最小花費，如果到不了的話輸出NO PATH。

樣例輸入

6 3 3 4

1 2 5

3 4 5

5 6 10

3 5 -100

4 6 -100

1 3 -10

樣例輸出

NO PATH

NO PATH

5

-95

-100

資料規模與約定

對于20%的資料，T<=100，R<=500，P<=500；

對于30%的資料，R<=1000，R<=10000，P<=3000；

對于100%的資料，1<=T<=25000，1<=R<=50000，1<=P<=50000。

這個題目是一個含有負邊的最短路問題，可以用SPFA過掉90%的資料，有2組資料過不了，大概是出題人針對SPFA而出的資料。

大概是我實力不濟，經過各種嘗試沒能卡過。于是決定改用dijkstra.

一般來說dijkstra是沒法處理含有負權值的圖的，但是這題給的圖比較特殊。

所有的負權值隻可能在航路，也就是單向邊中，而所有的單向邊都不在環中。

那麼整個圖就可以看做一個個用公路，也就是雙向邊連成的塊，塊與塊之間由一些單向邊連起來。

強連通縮點之後則變成一個有向無環圖……

有向無環圖的最短路可以DP出來……

于是想法就有了，首先用并查集維護所有公路連成的塊，然後從起點的塊開始，在塊的内部用dijkstra來求最短路。

塊與塊之間用類似拓撲排序的方式，維護一個塊的入度。當所有指向那個塊的單向邊的另一端的最短路都已經确定了，才開始在這個塊中求最短路。

代碼如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>

#define clr(a,b) memset(a, b, sizeof(a))

using namespace std;

const int N = 25050;
const int E = 150500;

//鄰接表
int h[N], v[E], w[E], nxt[E], el;
void initEdge() {
    clr(h, -1); el = 0;
}
void addEdge(int x, int y, int z) {
    v[el] = y; w[el] = z; nxt[el] = h[x]; h[x] = el++;
}

//并查集
int rt[N], ra[N];
int Find(int x) {
    if(x != rt[x]) rt[x] = Find(rt[x]);
    return rt[x];
}
void Union(int r1, int r2) {
    int x = Find(r1), y = Find(r2);
    if(x == y) return;
    if(ra[x] > ra[y]) rt[y] = x;
    else {
        rt[x] = y;
        if(ra[x] == ra[y]) ++ra[y];
    }
}
void Init(int n) {
    for(int i=0; i<=n; i++)
        ra[i] = 0, rt[i] = i;
}

struct EDGE {
    int u, v, w;
    bool flag;
    EDGE(){}
    EDGE(int x, int y, int z, bool f):u(x), v(y), w(z), flag(f){}
}   edge[E];

int edgel;

bool visitable[N];

void dfs(int x) {
    visitable[x] = true;
    for(int i=h[x]; ~i; i=nxt[i]) {
        if(!visitable[v[i]]) {
            dfs(v[i]);
        }
    }
}

int indegree[N];
bool vis[N];

//連結清單
int lh[N], lel, lv[E], lnxt[E];
void initLink() {
    clr(lh, -1); lel = 0;
}
void addLink(int x, int y) {
    lv[lel] = y; lnxt[lel] = lh[x]; lh[x] = lel++;
}

int dis[N];
bool tag[N];

int main() {
    int n, r, p, s;
    scanf("%d%d%d%d", &n, &r, &p, &s);
    Init(n);
    initEdge();
    edgel = 0;
    int x, y, z;
    for(int i=0; i<r; i++) {
        scanf("%d%d%d", &x, &y, &z);
        addEdge(x, y, z);
        addEdge(y, x, z);
        edge[edgel++] = EDGE(x, y, z, false);
        Union(x, y);
    }
    for(int i=0; i<p; i++) {
        scanf("%d%d%d", &x, &y, &z);
        addEdge(x, y, z);
        edge[edgel++] = EDGE(x, y, z, true);
    }
    dfs(s);
    initEdge();
    initLink();
    for(int i=0; i<edgel; i++) {
        if(visitable[edge[i].u] && visitable[edge[i].v]) {
            addEdge(edge[i].u, edge[i].v, edge[i].w);
            if(edge[i].flag) {
                ++ indegree[Find(edge[i].v)];
                addLink(Find(edge[i].v), edge[i].v);
            } else {
                addEdge(edge[i].v, edge[i].u, edge[i].w);
            }
        }
    }
    stack<int> zeroDegree;
    priority_queue<pair<int,int> > que;
    clr(dis, 0x3f);
    dis[s] = 0;
    que.push(make_pair(0, s));
    while(!que.empty() || !zeroDegree.empty()) {
        if(que.empty()) {
            int x = zeroDegree.top(); zeroDegree.pop();
            for(int i=lh[x]; ~i; i=lnxt[i]) {
                int y = lv[i];
                if(!vis[y]) {
                    vis[y] = true;
                    que.push(make_pair(-dis[y], y));
                }
            }
        } else {
            int x = que.top().second; que.pop();
            if(tag[x]) continue;
            tag[x]  = true;
            for(int i=h[x]; ~i; i=nxt[i]) {
                int y = v[i];
                if(!tag[y] && dis[y] > dis[x] + w[i]) {
                    dis[y] = dis[x] + w[i];
                    if(Find(x) == Find(y)) {
                        que.push(make_pair(-dis[y], y));
                    }
                }
                if(Find(x) != Find(y)) {
                    -- indegree[Find(y)];
                    if(indegree[Find(y)] == 0) {
                        zeroDegree.push(Find(y));
                    }
                }
            }
        }
    }
    for(int i=1; i<=n; i++) {
        if(visitable[i]) {
            printf("%d\n", dis[i]);
        } else {
            puts("NO PATH");
        }
    }

    return 0;
}