[SZKOpuł raj][POI2014]Rally
我从未见过有像SZKOpuł这样迷的OJ……
很好玩的一道题qwq
首先多源最短路太不好处理，我们搞一个超级源一个超级汇，分别和所有点连边。然后转成求超级源和超级汇的最长路。
我们不妨将这张图拓扑排序。然后我们思考对于拓扑排序得到的序列A，如果我们删除Ai的话，哪些路径不会收到影响？如果说有一个路径有一条边(u,v)，满足u和v在拓扑排序中分别位于Ai的两侧，那么这条路径不会受到影响。
反过来考虑每条边(u,v)，过这条边最优的路径一定是从源到u的最长路加上1再加上从v到汇的最长路（用两遍DP就能搞出来），他能影响的点在拓扑排序中显然事一段区间。
然后问题变成区间取max了，然后不需要在线，所以随便做了。
代码：
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 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 | #include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <utility>#include <queue>#include <vector>const int maxn = 500005;const int maxm = 750005;std::vector<int> G[maxn], RG[maxn];int inv[maxn], outv[maxn];void add_edge(int u, int v) { inv[v] ++; outv[u] ++; G[u].push_back(v); RG[v].push_back(u);}int T[maxn], ma[maxn];void toposort() { std::queue<int> Q; Q.push(0); int num = 0; while(!Q.empty()) { int u = Q.front(); Q.pop(); T[++ num] = u; ma[u] = num; for(auto v : G[u]) { inv[v] --; if(inv[v] == 0) Q.push(v); } }}int n, m;int f[maxn], g[maxn];int dp1(int x) { if(x == n + 1) return 0; if(f[x] != -1) return f[x]; f[x] = 0; for(auto v : G[x]) { f[x] = std::max(f[x], dp1(v) + 1); } return f[x];}int dp2(int x) { if(x == 0) return 0; if(g[x] != -1) return g[x]; g[x] = 0; for(auto v : RG[x]) { g[x] = std::max(g[x], dp2(v) + 1); } return g[x];}struct Interval { int l, r, v; bool operator <(const Interval &res) const { return v < res.v; }};int E[maxm][2]; std::vector<Interval> I;void pro_I() { memset(f, -1, sizeof(f)); memset(g, -1, sizeof(g)); for(int u = 0; u <= n + 1; u ++) { for(auto v : G[u]) { int l = ma[u], r = ma[v]; l ++; r --; if(l <= r) { Interval seg; seg.l = l; seg.r = r; seg.v = dp2(u) + dp1(v) + 1; I.push_back(seg); } } } std::sort(I.begin(), I.end());}const int maxno = maxn << 2;int setv[maxno];void pushdown(int o) { if(setv[o] != -1) { int lc = o << 1, rc = o << 1 | 1; setv[lc] = setv[o]; setv[rc] = setv[o]; setv[o] = -1; }}int ql, qr, v;void modify(int o, int L, int R) { if(ql <= L && R <= qr) { setv[o] = v; } else { pushdown(o); int M = (L + R) / 2; if(ql <= M) modify(o << 1, L, M); if(qr > M) modify(o << 1 | 1, M + 1, R); }}int ans[maxn];void dfs(int o, int L, int R) { if(L == R) { ans[L] = setv[o]; } else { pushdown(o); int M = (L + R) / 2; dfs(o << 1, L, M); dfs(o << 1 | 1, M + 1, R); }}int main() { memset(setv, -1, sizeof(setv)); scanf("%d%d", &n, &m); for(int i = 1; i <= m; i ++) { scanf("%d%d", &E[i][0], &E[i][1]); add_edge(E[i][0], E[i][1]); } for(int i = 1; i <= n; i ++) { if(true) { add_edge(0, i); } } for(int i = 1; i <= n; i ++) { if(true) { add_edge(i, n + 1); } } toposort(); pro_I(); for(auto &seg : I) { ql = seg.l, qr = seg.r, v = seg.v;#ifdef LOCAL printf("(%d, %d) -> %d\n", ql, qr, v);#endif modify(1, 1, n + 2); } dfs(1, 1, n + 2); int cho = 1, ret = 0x7fffffff; for(int i = 2; i <= n + 1; i ++) { if(ans[i] < ret) { cho = T[i]; ret = ans[i]; } } printf("%d %d\n", cho, ret - 2); return 0;} |
