P2296 寻找道路 题解

· · 题解

题解

首先感谢那些告诉我逆向思维的大佬们，这个题我也的确是用的逆向思维，但是跟其他大佬们的方法还是有一定差别的。（才不会告诉你我用其他题解的方法写挂了）。

我们可以这样理解题意，现在所有点都被他的出边束缚住了，有几个出边，就有几层束缚，而我们为了解救他们，从反向边往回广搜，如果遇到一个点，就使其的束缚减少一层，这样的话，最后没有束缚的点就是我们在最后求最短路时可以经过的点。那我们就可以用出度记录束缚（有没有发现像拓扑排序？）

所以我们可以这样做：

方法

  1. 我们可以先统计原图中每个点的出度。
  2. 反向搜索，并减少束缚。（注意：这里要记录每个边只能有一次减少束缚的机会，不然在广搜的时候，很有可能一条边会被搜到多次，从而导致答案错误）
  3. 判断哪些点可以走
  4. 跑最短路

代码：

ps:(将代码里无关紧要的代码进行了压行，如有不适，请谅解)

#include <bits/stdc++.h>
using namespace std;
struct edge {
    int from, to, nex;
} e[200100], ef[200010];
int n, m, s, t, a, b, cnt, out_degree[10010], lin[10010], linf[10010], check[10100], vis[10100], dis[10010], flag[200010];
inline void add(int a, int b)
{
    e[++cnt].from = a; e[cnt].to = b; e[cnt].nex = lin[a]; lin[a] = cnt; 
    ef[cnt].from = b; ef[cnt].to = a; ef[cnt].nex = linf[b]; linf[b] = cnt; 
    out_degree[a]++; 
}
inline void init()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    scanf("%d%d", &s, &t);
}
inline void bfs()
{
    queue <int> q;
    q.push(t);
    while(!q.empty())
    {
        int cur = q.front(); q.pop();
        for (int i = linf[cur]; i; i = ef[i].nex)
        {
            if (flag[i]) continue; flag[i] = 1;//坑：一条边只能减少一次
            if (!out_degree[ef[i].to])//坑：可能会导致程序崩溃
                    continue;
            out_degree[ef[i].to]--;
            q.push(ef[i].to);
        }
    }
}
inline void spfa()//死掉的算法
{
    for (int i = 1; i <= n; i++)
        dis[i] = 2147483647;
    queue <int> q;
    q.push(s);
    dis[s] = 0;
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        vis[cur] = 0;
        for (int i = lin[cur]; i; i = e[i].nex)
            if (check[e[i].to] && dis[cur] + 1 < dis[e[i].to])
            {
                dis[e[i].to] = dis[cur] + 1;
                if (!vis[e[i].to])
                    vis[e[i].to] = 1, q.push(e[i].to);
            }
    }
}
int main()
{
    init();
    bfs();
    for (int i = 1; i <= n; i++)//判断束缚是否已经消失
        if (!out_degree[i])
            check[i] = 1;
    spfa();
    printf("%d", dis[t]);
}