【NOIP2014提高组】寻找道路

https://www.luogu.org/problem/show?pid=2296

满足条件的路径：路径上的所有点的出边所指向的点都与终点连通。
反过来，不满足条件的路径：路径上至少一点的出边所指向的点不与终点连通。
考虑把所有与终点不连通的点以及指向他们的点都删掉，再一遍BFS求出最短路径。

具体做法：
对原图的转置图（将所有边的方向翻转得到的图）从终点开始一遍搜索，把传达不到的爱恋点以及在转置图中它们的所有出点全部标记。注意用两种不同的标记，否则会混乱。
最后在原图跑一遍BFS求出最短路径，有标记的点都不管。

#include <iostream>

#include <vector>

#include <queue>

#define maxn 10005

using namespace std;

int n, m, s, t;

vector<int> g[maxn], gt[maxn];

bool visited[maxn];

int dist[maxn];

int mark[maxn]; // 0/1表示该点与终点不连通/联通，-1表示该点指向标记0的点

void dfs(int k)

{

    mark[k] = ;

    for (int i = ; i < gt[k].size(); i++)

    {

        if (!visited[gt[k][i]])

        {

            visited[gt[k][i]] = true;

            dfs(gt[k][i]);

        }

    }

}

void bfs()

{

    queue<int> q;

    q.push(s);

    while (!q.empty() && dist[t] == )

    {

        int k = q.front();

        q.pop();

        if (mark[k] == )

        {

            for (int i = ; i < g[k].size(); i++)

            {

                if (!dist[g[k][i]])

                {

                    dist[g[k][i]] = dist[k] + ;

                    q.push(g[k][i]);

                }

            }

        }

    }

}

int main()

{

    cin >> n >> m;

    int a, b;

    for (int i = ; i <= m; i++)

    {

        cin >> a >> b;

        if (a != b)

        {

            g[a].push_back(b);

            gt[b].push_back(a);

        }

    }

    cin >> s >> t;

    dfs(t);

    for (int i = ; i <= n; i++)

    {

        if (mark[i] == )

        {

            for (int j = ; j < gt[i].size(); j++)

            {

                mark[gt[i][j]] = -;

            }

        }

    }

    bfs();

    cout << (dist[t] >  ? dist[t] : -) << endl;

    return ;

}

巴特西

【NOIP2014提高组】寻找道路

最新文章

热门文章