3832: [Poi2014]Rally
分析:
首先可以考虑删除掉一个点后,计算最长路。
设$f[i]$表示从起点到i的最长路,$g[i]$表示从i出发到终点的最长路。那么经过一条边的最长路就是$f[u]+1+g[v]$。
删除一个点后,这个点可能会使一些
代码:
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<cctype> #include<set> #include<queue> #include<vector> #include<map> using namespace std; typedef long long LL; inline int read() { int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1; for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f; } const int N = 500005; int g[N], f[N], T[N << 2], cnt[N << 2], q[N], n; struct Edge{ int to[N << 1], nxt[N << 1], head[N], En, deg[N << 1]; inline void add_edge(int u,int v) { ++En; to[En] = v, nxt[En] = head[u]; head[u] = En; deg[v] ++; } }Z, F; void solve() { int L = 1, R = 0; for (int i = 1; i <= n; ++i) if (F.deg[i] == 0) q[++R] = i; while (L <= R) { int u = q[L ++]; for (int i = F.head[u]; i; i = F.nxt[i]) { int v = F.to[i]; g[v] = max(g[v], g[u] + 1); if (!(--F.deg[v])) q[++R] = v; } } L = 1, R = 0; for (int i = 1; i <= n; ++i) if (Z.deg[i] == 0) q[++R] = i; while (L <= R) { int u = q[L ++]; for (int i = Z.head[u]; i; i = Z.nxt[i]) { int v = Z.to[i]; f[v] = max(f[v], f[u] + 1); if (!(--Z.deg[v])) q[++R] = v; } } } void update(int l,int r,int rt,int p,int v) { if (l == r) { cnt[rt] += v; if (cnt[rt] > 0) T[rt] = l; else T[rt] = -1, cnt[rt] = 0; return ; } int mid = (l + r) >> 1; if (p <= mid) update(l, mid, rt << 1, p, v); else update(mid + 1, r, rt << 1 | 1, p, v); T[rt] = max(T[rt << 1], T[rt << 1 | 1]); } int main() { n = read();int m = read(); for (int i = 1; i <= m; ++i) { int x = read(), y = read(); Z.add_edge(x, y); F.add_edge(y, x); } solve(); int ans = 1e9, pt; for (int i = 1; i <= n; ++i) update(0, n, 1, g[i], 1); for (int i = 1; i <= n; ++i) { int x = q[i]; for (int j = F.head[x]; j; j = F.nxt[j]) update(0, n, 1, g[x] + f[F.to[j]] + 1, -1); update(0, n, 1, g[x], -1); if (T[1] < ans) ans = T[1], pt = x; for (int j = Z.head[x]; j; j = Z.nxt[j]) update(0, n, 1, f[x] + g[Z.to[j]] + 1, 1); update(0, n, 1, f[x], 1); } cout << pt << " " << ans; return 0; }