noip_2014_寻找道路
题目描述
在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
- 路径上的所有点的出边所指向的点都直接或间接与终点连通.
- 在满足条件1的情况下使路径最短。
- 注意：图 G 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入输出格式
输入格式：
第一行有两个用一个空格隔开的整数 n 和 m，表示图有 n 个点和 m 条边。
接下来的 m 行每行 2 个整数 x，y。之间用一个空格隔开，表示有一条边从点 x 指向点y。
最后一行有两个用一个空格隔开的整数 s，t，表示起点为 s，终点为 t。
输出格式：
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出 -1 。
简吸
模拟赛的时候实在是想不到怎么找。
然后写了个floyed上去。骗了10分。
赛后看洛谷题解的时候，就感觉让人十分 niupi。
大概是这样：
我们可以将全部的点分为以下三类：
1.指向的点也能连接终点。
2.自己联通终点。
3.在图G上的点。
感觉这题的核心是建一个反向图筛点。
显然 3 类点已经读入，那么接下来是筛选 2 类点。
做法就是从终点开始广搜（反向图），搜到的做个标记就是2号店。
如果终点没有标记直接 return 0。
接下来是找 1 类点，做法是在有 2 类点中进行暴搜，对于 2 类点所连接的点进行判断，如果连接点不是 2 类点，那么这个点就不是 3 类点。
最后再用广搜找最短路。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define M 10010
int n,m,one[M],two[M],s,t,dis[M];
vector<int> edge[M];
vector<int> rev[M];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
edge[x].push_back(y);
rev[y].push_back(x);
}
scanf("%d%d",&s,&t);
two[t]=1;
queue<int> q;
q.push(t);
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=rev[now].size()-1;i>=0;i--){
int to=rev[now][i];
if(!two[to]){
q.push(to);
two[to]=1;
}
}
}
if(!two[s]){
cout<<-1;
return 0;
}
for(int i=1;i<=n;i++){
if(two[i]){
one[i]=1;
for(int j=edge[i].size()-1;j>=0;j--){
int to=edge[i][j];
if(!two[to]){
one[i]=0;
break;
}
}
}
}
if(!one[s]){
cout<<-1;
return 0;
}
dis[s]=1;
q.push(s);
while(!q.empty()){
int now=q.front();
q.pop();
if(now==t){
cout<<dis[t]-1;
return 0;
}
for(int i=edge[now].size()-1;i>=0;i--){
int to=edge[now][i];
if(one[to]&&!dis[to]){
dis[to]=dis[now]+1;
q.push(to);
}
}
}
cout<<-1;
return 0;
}
|
话说这段代码用控制变量法调了好久
2022-05-03 14:58:24