华师一附中OI组

标题: P1137 旅行计划 [打印本页]

---

作者: 胡雨菲菲    时间: 2018-6-7 13:08
标题: P1137 旅行计划


小明要去一个国家旅游。这个国家有 N 个城市，编号为 1 至 N ，并且有 M 条道路连接着，小明准备从其中一个城市出发，并只往东走到城市i停止。
所以他就需要选择最先到达的城市，并制定一条路线以城市i为终点，使得线路上除了第一个城市，每个城市都在路线前一个城市东面，并且满足这个前提下还希望游览的城市尽量多。
现在，你只知道每一条道路所连接的两个城市的相对位置关系，但并不知道所有城市具体的位置。现在对于所有的 i，都需要你为小明制定一条路线，并求出以城市 i 为终点最多能够游览多少个城市。

输入格式：

第 1 行为两个正整数 N,M 。
接下来 M 行，每行两个正整数 x,y ，表示了有一条连接城市 x 与城市 y 的道路，保证了城市 x 在城市 y 西面。
输出格式：
N 行，第 i 行包含一个正整数，表示以第 i 个城市为终点最多能游览多少个城市。
输入样例
5 6
1 2
1 3
2 3
2 4
3 4
2 5

输出样例
1
2
3
4
3

---

作者: 胡雨菲菲    时间: 2018-6-7 13:10

1. #include <cstdio>
   
2. #include <algorithm>
   
3. #include <queue>
   
4. using namespace std;
   
5. const int N = 100010;
   
6. 
   
7. int topo[N];
   
8. 
   
9. struct Edge {
   
10.     int v, nex;
    
11. }edge[N << 1]; int top;
    
12. 
    
13. struct Poi {
    
14.     int e, in, ans;
    
15. }poi[N];
    
16. 
    
17. inline void add(int x, int y) {
    
18.     top++;
    
19.     edge[top].v = y;
    
20.     edge[top].nex = poi[x].e;
    
21.     poi[x].e = top;
    
22.     return;
    
23. }
    
24. 
    
25. void toposort(int n) {
    
26.     queue<int> Q;
    
27.     for(int i = 1; i <= n; i++) {
    
28.         if(!poi[i].in) {
    
29.             Q.push(i);
    
30.         }
    
31.     }
    
32.     int t = 0;
    
33.     while(!Q.empty()) {
    
34.         int op = Q.front();
    
35.         Q.pop();
    
36.         topo[++t] = op;
    
37.         for(int i = poi[op].e; i; i = edge[i].nex) {
    
38.             int ed = edge[i].v;
    
39.             poi[ed].in--;
    
40.             if(!poi[ed].in) {
    
41.                 Q.push(ed);
    
42.             }
    
43.         }
    
44.     }
    
45.     return;
    
46. }
    
47. 
    
48. int main() {
    
49.     int m, n;
    
50.     scanf("%d%d", &n, &m);
    
51.     for(int i = 1, x, y; i <= m; i++) {
    
52.         scanf("%d%d", &x, &y);
    
53.         poi[x].in++;
    
54.         add(y, x);
    
55.     }
    
56.     toposort(n);
    
57. 
    
58.     for(int i = n; i >= 1; i--) {
    
59.         int op = topo[i];
    
60.         for(int i = poi[op].e; i; i = edge[i].nex) {
    
61.             int ed = edge[i].v;
    
62.             poi[op].ans = max(poi[op].ans, poi[ed].ans);
    
63.         }
    
64.         poi[op].ans++;
    
65.     }
    
66. 
    
67.     for(int i = 1; i <= n; i++) {
    
68.         printf("%d\n", poi[i].ans);
    
69.     }
    
70.     return 0;
    
71. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2