[BZOJ3832][Poi2014]Rally
试题描述
An annual bicycle rally will soon begin in Byteburg. The bikers of Byteburg are natural long distance cyclists. Local representatives of motorcyclists, long feuding the cyclists, have decided to sabotage the event.
There are intersections in Byteburg, connected with one way streets. Strangely enough, there are no cycles in the street network - if one can ride from intersection \(U\) to intersection \(V\) , then it is definitely impossible to get from \(V\) to \(U\).
The rally's route will lead through Byteburg's streets. The motorcyclists plan to ride their blazing machines in the early morning of the rally day to one intersection and completely block it. The cyclists' association will then of course determine an alternative route but it could happen that this new route will be relatively short, and the cyclists will thus be unable to exhibit their remarkable endurance. Clearly, this is the motorcyclists' plan - they intend to block such an intersection that the longest route that does not pass through it is as short as possible.
给定一个 \(N\) 个点 \(M\) 条边的有向无环图，每条边长度都是 \(1\)。
请找到一个点，使得删掉这个点后剩余的图中的最长路径最短。
输入
In the first line of the standard input, there are two integers, \(N\) and \(M\)(\(2 \le N \le 500 000,1 \le M \le 1 000 000\)), separated by a single space, that specify the number of intersections and streets in Byteburg. The intersections are numbered from \(1\) to \(N\). The lines that follow describe the street network: in the \(i+1\)-th of these lines, there are two integers, \(A_i, B_i\)(\(1 \le A_i,B_i \le N,A_i \ne B_i\)), separated by a single space, that signify that there is a one way street from the intersection no. \(A_i\) to the one no. \(B_i\).
第一行包含两个正整数 \(N,M\)(\(2 \le N \le 500 000,1 \le M \le 1 000 000\))，表示点数、边数。
接下来 \(M\) 行每行包含两个正整数 \(A[i],B[i]\)(\(1 \le A[i],B[i] \le N,A[i] \ne B[i]\))，表示 \(A[i]\) 到 \(B[i]\) 有一条边。
输出
The first and only line of the standard output should contain two integers separated by a single space. The first of these should be the number of the intersection that the motorcyclists should block, and the second - the maximum number of streets that the cyclists can then ride along in their rally. If there are many solutions, your program can choose one of them arbitrarily.
包含一行两个整数 \(x,y\)，用一个空格隔开，\(x\) 为要删去的点，\(y\) 为删除 \(x\) 后图中的最长路径的长度，如果有多组解请输出任意一组。
输入示例
6 5
1 3
1 4
3 6
3 4
4 5输出示例
1 2数据规模及约定
见“输入”
题解
首先建立 \(S\) 和 \(T\)，\(S\) 向所有点连边，所有点向 \(T\) 连边，那么原图中的最长路就等于现在 \(S\) 到 \(T\) 的最长路减 \(2\) 了。
考虑给每条边赋权值，权值即为经过这条边的最长路的长度，这个权值显然很好计算，正反 dp 一下就好了。
然后我们枚举删每个点之后的最长路分别是多少。我们按照拓扑序枚举这个点；首先将所有从 \(S\) 出发的边的边权加到堆中，然后将枚举的点 \(x\) 的入边全都删掉；当枚举的点 \(x\) 变成 \(x'\) 时，将 \(x\) 的出边加入，\(x'\) 的入边删掉；这样能保证任意时刻在堆中的路径都是不经过当前的 \(x\)，并且包含所有可能出现的最长路径。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 500010
#define maxm 2000010
#define oo 2147483647
int n, S, T, ind[maxn];
struct Edge {
int a, b, c;
Edge() {}
Edge(int _, int __): a(_), b(__) {}
} es[maxm];
struct Graph {
int m, head[maxn], nxt[maxm], to[maxm], id[maxm];
void AddEdge(int a, int b, int i) {
to[++m] = b; id[m] = i; nxt[m] = head[a]; head[a] = m;
return ;
}
} G, rG;
int hd, tl, Qd[maxn];
int ds[maxn], dt[maxn];
priority_queue <int> Q, delQ;
int main() {
n = read(); int m = read();
rep(i, 1, m) {
int a = read(), b = read();
G.AddEdge(a, b, i); rG.AddEdge(b, a, i);
es[i] = Edge(a, b);
ind[b]++;
}
S = n + 1; T = n + 2;
rep(i, 1, n) {
G.AddEdge(S, i, m + i);
es[m+i] = Edge(S, i);
G.AddEdge(i, T, m + n + i);
es[m+n+i] = Edge(i, T);
rG.AddEdge(i, S, m + i);
rG.AddEdge(T, i, m + n + i);
ind[i]++; ind[T]++;
}
n += 2;
hd = tl = 0;
rep(i, 1, n) if(!ind[i]) Qd[++tl] = i;
while(hd < tl) {
int u = Qd[++hd];
for(int e = G.head[u]; e; e = G.nxt[e]) if(!--ind[G.to[e]]) Qd[++tl] = G.to[e];
}
rep(i, 1, n) {
int u = Qd[i];
for(int e = G.head[u]; e; e = G.nxt[e]) ds[G.to[e]] = max(ds[G.to[e]], ds[u] + 1);
}
dwn(i, n, 1) {
int u = Qd[i];
for(int e = G.head[u]; e; e = G.nxt[e]) dt[u] = max(dt[u], dt[G.to[e]] + 1);
}
int cnte = m + (n - 2 << 1);
rep(i, 1, cnte) es[i].c = ds[es[i].a] + 1 + dt[es[i].b]; // , printf("%d -> %d %d\n", es[i].a, es[i].b, es[i].c);
for(int e = G.head[Qd[1]]; e; e = G.nxt[e]) Q.push(es[G.id[e]].c);
int mn = oo, mnp;
rep(i, 2, n - 1) {
int u = Qd[i];
for(int e = rG.head[u]; e; e = rG.nxt[e]) {
delQ.push(es[rG.id[e]].c);
while(!delQ.empty() && delQ.top() == Q.top()) delQ.pop(), Q.pop();
}
if(i > 2) {
int v = Qd[i-1];
for(int e = G.head[v]; e; e = G.nxt[e]) {
Q.push(es[G.id[e]].c);
while(!delQ.empty() && delQ.top() == Q.top()) delQ.pop(), Q.pop();
}
}
assert(!Q.empty());
if(Q.top() < mn) mn = Q.top(), mnp = u;
}
printf("%d %d\n", mnp, mn - 2);
return 0;
}