信息学奥赛一本通 1885：【14NOIP提高组】寻找道路 | 洛谷 P2296 [NOIP2014 提高组] 寻找道路

【题目链接】

洛谷 P2296 [NOIP2014 提高组] 寻找道路
ybt 1885：【14NOIP提高组】寻找道路

【题目考点】

1. 图论：广搜

2. 图论：反图

【解题思路】

设path数组，path[i]表示顶点i出发到终点t是否有路径。
先求path数组，需要对原图建反图，而后从终点t开始进行广搜，广搜过程中访问到的顶点x，表示在反图中从t出发到顶点x有路径，也就是在正图中从顶点x到终点t存在路径。
设sel数组，sel[i]为真表示顶点i可以作为该题要选择的符合条件的路径上的点。
而后遍历所有顶点，对于顶点i，如果i到t有路径，且i的邻接点到t都有路径，那么顶点i可以作为符合条件的路径上的点。
最后从起点s出发进行广搜，求符合条件的路径的最短路径长度。求出从s出发到所有满足sel[i]为真的顶点i的最短路径长度dis[i]。最后dis[t]就是结果。

【题解代码】

解法1：广搜

#include <bits/stdc++.h>
using namespace std;
#define N 10005
bool vis[N], path[N], sel[N];//path[i]:i到t有路径  sel[i]：i以及i的邻接点都到t有路径 
int n, m, s, t, dis[N];
vector<int> g[N], rg[N];//g:正图 rg:反图 
void bfs1()
{
queue<int> que;
vis[t] = true;
que.push(t);
while(!que.empty())
{
int u = que.front();
que.pop();
path[u] = true;
for(int v : rg[u]) if(!vis[v])
{
vis[v] = true;
que.push(v);
}
}
}
int bfs2()
{
if(sel[s] == false)
return -1;
queue<int> que;
vis[s] = true;
que.push(s);
while(!que.empty())
{
int u = que.front();
que.pop();
if(u == t)
return dis[u];
for(int v : g[u]) if(!vis[v] && sel[v])
{
vis[v] = true;
dis[v] = dis[u]+1; 
que.push(v);
} 
}
return -1;
} 
bool check(int u)
{
if(!path[u]) 
return false;
for(int v : g[u]) if(!path[v])
return false;
return true;
}
int main()
{
int x, y;
cin >> n >> m;
for(int i = 1; i <= m; ++i)
{
cin >> x >> y;
g[x].push_back(y);
rg[y].push_back(x);
}
cin >> s >> t;
bfs1();
for(int i = 1; i <= n; ++i)
sel[i] = check(i);
memset(vis, 0, sizeof(vis));
cout << bfs2(); 
return 0;
} 

原文地址：https://blog.csdn.net/lq1990717/article/details/142711907

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！