P3573 [POI2014]RAJ-Rally

P3573 [POI2014]RAJ-Rally

题意：
给定一个N个点M条边的有向无环图，每条边长度都是1。
请找到一个点，使得删掉这个点后剩余的图中的最长路径最短。
$N,M(2<=N<=500000,1<=M<=1000000)$

思路：
转化一下问题，给定 一张DAG，对于每个点计算，删除该点，图上的最长路，对所有点的答案取min即可。

首先分析问题：
可以先找到原图中的最长路，那么删除最长路之外的点，并不会影响原图的最长路；
接下来就是删除最长路上的点：
这有两种情况，一、删除的点使原图的连通性不变，二、删除点使原图的连通性发生改变了。
对于第二种情况比较好处理，就从直径的端点跑一次正反bfs即可。
难处理的是 第一种情况，比较复杂，读者自行思考233

另一个方案：
由于是 DAG，首先想到拓扑排序。先对 DAG 拓扑排序一遍，然后求出分别以 $i$ 号点为开头与结尾的最长路径 $S_i$和 $T_i$。那么对于原图中的一条边 $u\to v$，经过这条边的最长路径的长度为 $S_u+T_v+1$。这样删点就可以看成删除一条条边。
然后考虑如下性质：对于一个点 $i$，设拓扑序在其之前的点 点集为 $S$，拓扑序在其之后的点 点集为 $T$。那么最长路 就分为三种情况：
一、以$u$为终点的 最长路，$u\in S$。
二、以$v$为起点的 最长路，$v\in T$。
三、过 $u?>v$这条边的最长路，$u\in S$,$v\in T$。

那么考虑 不经过点$i$的最长路，假设当前点还在$T$集合中，那么当前所有路径中 不合法的路径 只有两种：
一、以$i$为起点的最长路
二、经过$u?>i$这条边的最长路

把所有可能的最长路 去掉这两种不合法的情况，剩下的最长路就是 不经过点$i$的最长路，即删除点$i$ 的最长路。

因此，我们按照 拓扑序来枚举点，初始所有点都在集合$T$中。在得到删除点$i$的最长路之后，需要维护$S$和$T$集合，即 将点$i$加入到$S$集合中，并且 加入所有经过$i$的出边的最长路 到合法路径集合。

维护这个信息，需要做到插入一个数、删除一个数、查询最大值，可以用权值线段树，也可以用 multiset。

详情见代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const ll mod=998244353;ll n,m;
struct node{
    int s,e,next;
}z1[1000050],z2[1000050];
ll len1,len2;
ll head1[500050],head2[500050];
int du1[500050],du2[500050];
void add1(ll a,ll b){
    z1[len1].s=a;z1[len1].e=b;z1[len1].next=head1[a];head1[a]=len1++;
}
void add2(ll a,ll b){
    z2[len2].s=a;z2[len2].e=b;z2[len2].next=head2[a];head2[a]=len2++;
}
int f[500050],g[500050];
queue<int>q;
int id[500050];//topo序 
void solve1(){
    int cnt=0;for(int i=1;i<=n;i++){
    if(du1[i]==0)q.push(i);}while(!q.empty()){
    int x=q.front();q.pop();id[++cnt]=x;for(int i=head1[x];i!=-1;i=z1[i].next){
    int to=z1[i].e;du1[to]--;f[to]=max(f[to],f[x]+1);if(du1[to]==0){
    q.push(to);}}}
}
void solve2(){
    for(int i=1;i<=n;i++){
    if(du2[i]==0)q.push(i);}while(!q.empty()){
    int x=q.front();q.pop();for(int i=head2[x];i!=-1;i=z2[i].next){
    int to=z2[i].e;du2[to]--;g[to]=max(g[to],g[x]+1);if(du2[to]==0){
    q.push(to);}}}
}
int tr[2000060],res[500050];
void update(int p,int l,int r,int x,int v){
    if(l==r){
    res[x]+=v;if(res[x]>0)tr[p]=l;else tr[p]=-1;return ;}int mid=l+r>>1;if(x<=mid)update(2*p,l,mid,x,v);else update(2*p+1,mid+1,r,x,v);tr[p]=max(tr[2*p],tr[2*p+1]);
}int main(){
    scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++)head1[i]=-1,head2[i]=-1;for(int i=1;i<=m;i++){
    int a,b;scanf("%d%d",&a,&b);add1(a,b);add2(b,a);du1[b]++;du2[a]++;}solve1();solve2();for(int i=1;i<=n;i++){
    update(1,0,n,g[i],1);}int ans=n+1,idd;for(int i=1;i<=n;i++){
    int x=id[i];for(int j=head2[x];j!=-1;j=z2[j].next){
    int to=z2[j].e;update(1,0,n,f[to]+g[x]+1,-1);}update(1,0,n,g[x],-1);if(tr[1]<ans)ans=tr[1],idd=x;for(int j=head1[x];j!=-1;j=z1[j].next){
    int to=z1[j].e;update(1,0,n,f[x]+g[to]+1,1);}update(1,0,n,f[x],1);}printf("%d %d\n",idd,ans);return 0;
}