洛谷 车站分级

题号:P1983
算法标签:拓扑排序
洛谷题解地址:https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1983
参考题解:作者: chenshaoqian 更新时间: 2016-09-25 21:08
作者: mangoyang 更新时间: 2016-09-24 17:20

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<list>
#include<stack>
using namespace std;
#define virtual_point_start 1000
int n, m;
int s[1005];
int virtual_point_ptr = virtual_point_start;
int indegree[3000];
int pass[1005][1005];
int path_dis[3000];
list<int> edge[3000];
vector<int> t_edge_to;
stack<int> cur_level;
bool execute(){
    while (!cur_level.empty())cur_level.pop();
    for (int i = 1; i <= n; i++){
        if (indegree[i] == 0){
            cur_level.push(i);
            indegree[i] = -1;
        }
    }
    for (int i = 1001; i <= virtual_point_ptr; i++){
        if (indegree[i] == 0){
            cur_level.push(i);
            indegree[i] = -1;
        }
    }
    if (cur_level.empty())return false;
    while (!cur_level.empty()){
        int cur = cur_level.top();
        cur_level.pop();
        for (list<int>::iterator iter = edge[cur].begin(); iter != edge[cur].end(); iter++){
            indegree[*iter]--;
            int point_dis = (cur <= 1000);
            path_dis[*iter] = max(path_dis[*iter],path_dis[cur] + point_dis);
        }
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)cin >> pass[i][j];
        t_edge_to.clear();
        int ptr = 1;
        for (int j = pass[i][1]; j <= pass[i][s[i]]; j++){
            if (pass[i][ptr] == j)ptr++;
            else t_edge_to.push_back(j);
        }
        virtual_point_ptr++;
        for (vector<int>::iterator iter = t_edge_to.begin(); iter != t_edge_to.end(); iter++){
            edge[virtual_point_ptr].push_back(*iter);
            indegree[*iter]++;
        }
        for (int se = 1; se <= s[i]; se++){
            edge[pass[i][se]].push_back(virtual_point_ptr);
            indegree[virtual_point_ptr]++;
        }
    }
    while (execute());
    int ans = 0;
    for (int i = 1; i <= n; i++){
        ans = max(ans, path_dis[i]);
    }
    cout << ans+1;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注