P3573 [POI2014] RAJ-Rally
题意
给一张 \(DAG\)，问删去一个点的最长路是多少。
题解
好妙的题。
考虑对于每个点求出删除此点之后的最长路。
考虑到一个 \(DAG\) 只会由拓扑序低的点走向高的点。
所以我们按照拓扑序枚举点删除之后的最短路。
考虑根据当前点的拓扑序将点集划分为两个集合 \(S\) 和 \(T\) 。
我们先求出以每个点为终点和起点的最长路。
\(S\) 中维护每个点为终点的长度，\(T\) 中维护为起点的长度，同时维护 \(S->T\) 的所有路径。
显然跨过两个集合的路径可以用一条边描述，也就是两端拼起来。
考虑删除一个点的影响是什么，发现同时会影响的是从 \(S\) 中指向这个点的路径。
删掉之后将其加入 \(S\)，然后将跨过集合的边加入就好了，用 multiset 维护即可。
这道题的突破点就在于按照拓扑序枚举我们需要维护的东西变化很小。
点击查看代码
#include <bits/stdc++.h>
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
x = 0 ;rg int f(0) ; rg char c(gc()) ;
while(!isdigit(c)) f |= (c=='-'),c = gc() ;
while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
x = (f?-x:x) ;
read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
if(x < 0) pc('-'),x = -x ;
do stk[++tp] = x%10,x /= 10 ; while(x) ;
while(tp) pc(stk[tp--]^48) ; space ;
print(p...) ;
}
bool S_GND ;
const int N = 1e6+5 ;
int n,m,ans,pos,top ;
int d[N],b[N],f[N],g[N],id[N] ;
vector<int>q[N],p[N] ;
void Solve1()
{
queue<int>que ;
FOR(i,1,n,1) if(!d[i]) que.push(i) ;
while(!que.empty())
{
int x = que.front() ; que.pop() ;
id[++top] = x ;
for(auto v:q[x])
{
d[v]--,f[v] = max(f[v],f[x]+1) ;
if(!d[v]) que.push(v) ;
}
}
}
void Solve2()
{
queue<int>que ;
FOR(i,1,n,1) if(!b[i]) que.push(i) ;
while(!que.empty())
{
int x = que.front() ; que.pop() ;
for(auto v:p[x])
{
b[v]--,g[v] = max(g[v],g[x]+1) ;
if(!b[v]) que.push(v) ;
}
}
}
multiset<int>s ;
signed main()
{
//cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
// freopen(".in","r",stdin) ;
// freopen(".out","w",stdout) ;
read(n,m) ;
FOR(i,1,m,1)
{
int u,v ; read(u,v) ;
q[u].pb(v),p[v].pb(u),d[v]++,b[u]++ ;
}
Solve1(),Solve2() ;
FOR(i,1,n,1) s.insert(-g[i]) ;
ans = -*s.begin() ;
// FOR(i,1,n,1) print(id[i]) ; enter ;
// FOR(i,1,n,1) print(f[i]) ; enter ;
// FOR(i,1,n,1) print(g[i]) ; enter ;
FOR(t,1,n,1)
{
int i = id[t] ; //print(i),enter ;
s.erase(s.find(-g[i])) ;
for(auto v:p[i]) s.erase(s.find(-f[v]-1-g[i])) ;
auto it = s.begin() ; if(-*it < ans) ans = -*it,pos = i ;
s.insert(-f[i]) ; //print(-*it),enter ;
for(auto v:q[i]) s.insert(-f[i]-1-g[v]) ;
}
print(pos,ans) ;
return 0 ;
}