日度归档：3 11 月, 2017

洛谷 车站分级

发表评论

题号：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;
}

20180814更新：
题解：https://www.luogu.org/blog/24212/solution-p1983
主要是借鉴了一个开一个二维数组判断边是否加重的问题。
还有一个最重要的就是“由停车的站向不停车的站连边”问题，总是考虑不到。

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
#include<iostream>
#include<vector>
using namespace std;
int n,m;
bool visited[1002][1002];
int inDegree[1002],grades[1002];
vector<int> edges[1002];
vector<int> railStation;
vector<int> unStopStation;
vector<int> curGrade;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        railStation.clear();
        unStopStation.clear();
        int num;
        cin>>num;
        for(int j=1;j<=num;j++){
            int t;
            cin>>t;
            railStation.push_back(t);
        }
        for(int j=0;j<railStation.size()-1;j++){
            for(int k=railStation[j]+1;k<railStation[j+1];k++){
                unStopStation.push_back(k);
            }
        }
        for(int j=0;j<railStation.size();j++){
            for(int k=0;k<unStopStation.size();k++){
                if(visited[railStation[j]][unStopStation[k]])continue;
                visited[railStation[j]][unStopStation[k]]=true;
                edges[railStation[j]].push_back(unStopStation[k]);
                inDegree[unStopStation[k]]++;
            }
        }
    }
    int maxV=0;
    do{
        curGrade.clear();
        for(int i=1;i<=n;i++){
            if(inDegree[i]==0){
                curGrade.push_back(i);
                inDegree[i]--;
            }
        }
        for(int i=0;i<curGrade.size();i++){
            grades[curGrade[i]]++;
            for(int j=0;j<edges[curGrade[i]].size();j++){
                grades[edges[curGrade[i]][j]]=max(grades[edges[curGrade[i]][j]],grades[curGrade[i]]);
                inDegree[edges[curGrade[i]][j]]--;
            }
            maxV=max(maxV,grades[curGrade[i]]);
        }
    }while(curGrade.size());
    cout<<maxV;
}