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