【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 ;
}
上一篇:[ETL实践指南]基于Kettle的MaxCompute插件实现数据上云


下一篇:安全的API接口解决方案