题解 P3573 【[POI2014]RAJ-Rally】

AquaRio

2019-10-27 16:57:14

Solution

突然发现所有的题解都没有用multiset。 其它题解都是用权值线段树,或者是堆解决的问题。 但是权值线段树码量太大,堆跑得很慢。 为什么不了解一下~~又好写又跑得快~~的multiset呢? ```cpp // P3573.CPP #include<bits/stdc++.h> using namespace std; const int N = 5e5 + 5; const int M = 1e6 + 5; int n, m; multiset<int> S; struct edge { int v, nxt; } e[M << 1]; int head[2][N], cnt, in[N], q[N], l, r; int dis[2][N]; inline void add(int u, int v, int t) { e[++cnt].v = v; e[cnt].nxt = head[t][u]; head[t][u] = cnt; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); in[v]++; add(u, v, 0); add(v, u, 1); } int pos = 0, dismin = n, tmp; for (int i = 1; i <= n; i++) if (in[i] == 0) q[r++] = i; while (l < r) { int fr = q[l]; l++; for (int i = head[0][fr]; i; i = e[i].nxt) { int to = e[i].v; in[to]--; if (!in[to]) q[r++] = e[i].v; } } for (int k = 0; k <= n - 1; k++) for (int i = head[0][q[k]]; i; i = e[i].nxt) dis[0][e[i].v] = max(dis[0][e[i].v], dis[0][q[k]] + 1); for (int k = n - 1; k >= 0; k--) for (int i = head[1][q[k]]; i; i = e[i].nxt) dis[1][e[i].v] = max(dis[1][e[i].v], dis[1][q[k]] + 1); for (int i = 1; i <= n; i++) S.insert(dis[1][i]); for (int k = 0; k <= n - 1; k++) { S.erase(S.find(dis[1][q[k]])); for (int i = head[1][q[k]]; i; i = e[i].nxt) S.erase(S.find(dis[0][e[i].v] + dis[1][q[k]] + 1)); tmp = *S.rbegin(); if (tmp < dismin) dismin = tmp, pos = q[k]; for (int i = head[0][q[k]]; i; i = e[i].nxt) S.insert(dis[0][q[k]] + dis[1][e[i].v] + 1); S.insert(dis[0][q[k]]); } cout << pos << " " << dismin << endl; } ```