BZOJ3832: [Poi2014]Rally(拓扑排序 堆)
程序员文章站
2022-10-18 23:45:09
题意 "题目链接" Sol 最直观的思路是求出删除每个点后的最长路,我们考虑这玩意儿怎么求 设$f[i]$表示以$i$结尾的最长路长度,$g[i]$表示以$i$开始的最长路长度 根据DAG的性质,显然我们删除一个点后,整个集合会被分成两部分:拓扑序小于/大于当前点 那么此时的最长路一定可以通过计算连 ......
题意
sol
最直观的思路是求出删除每个点后的最长路,我们考虑这玩意儿怎么求
设\(f[i]\)表示以\(i\)结尾的最长路长度,\(g[i]\)表示以\(i\)开始的最长路长度
根据dag的性质,显然我们删除一个点后,整个集合会被分成两部分:拓扑序小于/大于当前点
那么此时的最长路一定可以通过计算连接着两个集合的边\((u, v)\)的\(f(u) + f(v) +1\)得到
这样的话我们可以直接维护边集,在统计每个点的答案的时候首先删掉入边的贡献统计答案,统计完后再加入出边的贡献
显然线段树可以维护,其实堆也可以维护,具体见代码(抄袭自yyb大佬)
#include<bits/stdc++.h> #define chmax(x, y) (x = (x > y ? x : y)) #define chmin(x, y) (x = (x < y ? x : y)) using namespace std; const int maxn = 1e6 + 10, inf = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, a1 = inf, a2; class mypriorityqueue { public: priority_queue<int> q1, q2; void push(int x) { q1.push(x); } int pop(int x) { q2.push(x); } bool empty() { while(!q2.empty() && (q1.top() == q2.top())) q1.pop(), q2.pop(); return q1.size() == 0; } int top() { return empty() ? inf : q1.top(); } }; mypriorityqueue q; struct graph { vector<int> v[maxn]; int f[maxn], inder[maxn], id[maxn], tot; graph() { tot = 0; } void addedge(int x, int y) { v[x].push_back(y); inder[y]++; } void topsort() { queue<int> q; for(int i = 1; i <= n; i++) if(!inder[i]) q.push(i); while(!q.empty()) { int p = q.front(); q.pop(); id[++tot] = p; for(int i = 0; i < v[p].size(); i++) { int to = v[p][i]; chmax(f[to], f[p] + 1); if(!(--inder[to])) q.push(to); } } } }; graph gs, gt; int main() { n = read(); m = read(); for(int i = 1; i <= m; i++) { int x = read(), y = read(); gs.addedge(x, y); gt.addedge(y, x); } gs.topsort(); gt.topsort(); for(int i = 1; i <= n; i++) q.push(gt.f[i]); for(int t = 1; t <= n; t++) { int x = gs.id[t]; q.pop(gt.f[x]); for(int i = 0; i < gt.v[x].size(); i++) { int to = gt.v[x][i]; q.pop(gs.f[to] + gt.f[x] + 1); } int now = q.top(); q.push(gs.f[x]); if(now < a1) a1 = now, a2 = x; for(int i = 0; i < gs.v[x].size(); i++) { int to = gs.v[x][i]; q.push(gs.f[x] + gt.f[to] + 1); } } printf("%d %d\n", a2, a1); return 0; }