题解【洛谷P3008】[USACO11JAN]Roads and Planes G

题意简述：

有一个 (T) 个点，(R) 条双向边，(P) 条单向边的图。其中双向边权值均为正，单向边权值可为负。

保证如果有一条航线可以从 (a) 到 (b)，那么保证不可能通过一些道路和航线从 (b) 回到 (a)。

请你求出 (S) 到所有点的最短距离。如果不能到达，输出 NO PATH。

( ext{Data Range})： (1leq Tleq 25000)，(1leq R,Pleq50000),

首先声明：在这一题中使用 SPFA 求最短路会被卡。

于是我们考虑从题目中挖掘一些性质来解决该题。

我们看到这一句话：

保证如果有一条航线可以从 (a) 到 (b)，那么保证不可能通过一些道路和航线从 (b) 回到 (a)。

这句话说明：这个图不存在负环，有可能有正环。

也就是说，如果只把双向边添加进来，那么一定就形成了若干个连通的块。

放个图可能更好理解：

题解【洛谷P3008】[USACO11JAN]Roads and Planes G

然后我们再将单向边添加进来，就可以考虑对连通块和一些单向边组成的图进行拓扑排序。

在拓扑排序之后，对于当前的连通块，我们考虑对连通块内部的点进行一次 Dijkstra 算法。

在进行 Dijkstra 算法时，一开始先将每一个点插入堆中，然后我们每次取出堆中的最小值，遍历与那个点相连的点：

如果可以更新最短距离，就更新；并且如果它们处于同一个连通块中，就将遍历到的点插入堆中。
如果它们不处于同一个连通块中，就将遍历到的点所在的连通块的入度减 (1)；如果减 (1) 后入度为 (0)，那么就将那一个连通块插入拓扑排序的队列里。

最后输出的时候，有一个小技巧来判断无解：如果 (dist_i > frac{INF}{2})，那么就说明无解。这是为了判断无法到达时还用负数去更新 (INF) 的情况。

这里可能讲的不是很清楚，还要自己去想一下……

代码有点长……

#include <bits/stdc++.h>

using namespace std;

const int N = 25003, M = 150003, INF = 0x3f3f3f3f;

int n, m, r, p, S;
int tot, head[N], ver[M], edge[M], nxt[M];
int id[N]; //每个点所在的连通块编号
int cnt_block; //块的个数
vector <int> block[N]; //每个连通块内部的点
int in[N]; //拓扑排序的入度
queue <int> q; //拓扑排序的队列
int dist[N], vis[N]; //最短距离 和 Dijkstra 中判断是否入过队 的 vis 数组

inline void add(int u, int v, int w) //邻接表加边
{
    ver[++tot] = v, edge[tot] = w, nxt[tot] = head[u], head[u] = tot;
}

void dfs(int u, int nowid) //对连通块内部的点进行标记
{
    id[u] = nowid;
    block[nowid].push_back(u);
    for (int i = head[u]; i; i = nxt[i])
    {
        int v = ver[i];
        if (!id[v])
            dfs(v, nowid);
    }
}

inline void Dijkstra(int now)
{
    priority_queue <pair <int, int> > qh; //定义一个堆
    int len = block[now].size();
    for (int i = 0; i < len; i+=1) 
        qh.push(make_pair(-dist[block[now][i]], block[now][i])); //先将连通块中的元素加入堆中
    while (!qh.empty())
    {
        int u = qh.top().second; qh.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = nxt[i])
        {
            int v = ver[i], w = edge[i];
            if (dist[v] > dist[u] + w) //更新最短距离
            {
                dist[v] = dist[u] + w;
                if (id[v] == id[u])
                    qh.push(make_pair(-dist[v], v)); //在同一个块中就加进堆
            }
            if (id[v] != id[u] && --in[id[v]] == 0) //下一个块可以进行拓扑排序
                q.push(id[v]);
        }
    }
}

inline void toposort()
{
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0; //初始化最短距离
    for (int i = 1; i <= cnt_block; i+=1)
        if (!in[i])
            q.push(i); //先加入入度为 0 的点
    while (!q.empty())
    {
        int t = q.front(); q.pop();
        Dijkstra(t); //对每一个连通块做 Dijkstra
    }
}

int main()
{
    scanf("%d%d%d%d", &n, &r, &p, &S);
    for (int i = 1; i <= r; i+=1)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
    }
    for (int i = 1; i <= n; i+=1) //求出每个点所在的连通块编号
        if (id[i] == 0) 
        {
            ++cnt_block;
            dfs(i, cnt_block);
        }
    for (int i = 1; i <= p; i+=1)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        ++in[id[v]]; //统计入度
    }
    toposort(); //进行拓扑排序
    for (int i = 1; i <= n; i+=1)
        if (dist[i] > INF / 2) puts("NO PATH"); //判断无解
        else printf("%d
", dist[i]); //输出最短距离
    return 0;
}

题解【洛谷P3008】[USACO11JAN]Roads and Planes G

相关推荐