BZOJ3832 [Poi2014]Rally 【拓扑序 + 堆】
发布日期:2021-08-16 15:55:42 浏览次数:5 分类:技术文章

本文共 2423 字,大约阅读时间需要 8 分钟。

题目链接

题解

神思路orz,根本不会做

\(f[i]\)为到\(i\)的最长路,\(g[i]\)\(i\)出发的最长路,二者可以拓扑序后\(dp\)求得
那么一条边\((u,v)\)的对应的最长链就是\(f[u] + 1 + g[v]\)
我们人为加入源汇点\(S\)\(T\)\(S\)向每个点连边,每个点向\(T\)连边
我们考虑把整个图划分开
一开始所有点都在\(T\)这边,割边为所有\(S\)的边
然后我们按照拓扑序把点逐一加入\(S\)集合中
加入时,我们删去\(S\)集合连向该点的边,然后询问所有边的最大值,即为删去该点的最长链
加入后,我们加入该点连向\(T\)集合的边
由于是按照拓扑序,所以以上提到的所有边就是该点的所有入边/出边

然后所有边的最大值可以用堆或者线段树维护

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #define Redge(u) for (int k = h[u]; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define mp(a,b) make_pair
           
            (a,b)#define cls(s) memset(s,0,sizeof(s))#define cp pair
            
             #define LL long long intusing namespace std;const int maxn = 500005,maxm = 2000005,INF = 1000000000;inline int read(){
             
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;}struct Heap{
priority_queue  a,b;
void ck(){while (!b.empty() && a.top() == b.top()) a.pop(),b.pop();}
int size(){return a.size() - b.size();}
void ins(int x){ck(); a.push(x);}
void del(int x){ck(); b.push(x);}
int top(){ck(); return size() ? a.top() : 0;}}H;int n,m,f[maxn],g[maxn],s[maxn];int q[maxn],head,tail;int h[maxn],de[maxn],ne;int hi[maxn],nei;struct EDGE{int to,nxt;}ed[maxm],e[maxm];inline void build(int u,int v){
ed[++ne] = (EDGE){v,h[u]}; h[u] = ne;
de[v]++;
e[++nei] = (EDGE){u,hi[v]}; hi[v] = nei;}void topu(){
head = 0; tail = -1; int u;
REP(i,n) if (!de[i]) q[++tail] = i;
REP(i,n){
s[i] = u = q[head++];
Redge(u) if (!(--de[ed[k].to])) q[++tail] = ed[k].to;
}}void init(){
REP(i,n){
int u = s[i];
Redge(u) f[ed[k].to] = max(f[ed[k].to],f[u] + 1);
}
for (int i = n; i; i--){
int u = s[i];
Redge(u) g[u] = max(g[u],g[ed[k].to] + 1);
}}void solve(){
int ans = INF,ansu = 0,x;
REP(i,n) H.ins(g[i]);
REP(i,n){
int u = s[i];
H.del(g[u]);
for (int k = hi[u]; k; k = e[k].nxt)
H.del(f[e[k].to] + 1 + g[u]);
x = H.top();
if (x < ans) ans = x,ansu = u;
H.ins(f[u]);
Redge(u) H.ins(f[u] + 1 + g[ed[k].to]);
}
printf("%d %d\n",ansu,ans);}int main(){
n = read(); m = read();
int a,b;
REP(i,m){
a = read(); b = read();
build(a,b);
}
topu();
init();
//REP(i,n) printf("node%d  f = %d   g = %d\n",i,f[i],g[i]);
solve();
return 0;}

转载于:https://www.cnblogs.com/Mychael/p/9097788.html

转载地址:https://blog.csdn.net/weixin_30810239/article/details/98612048 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:BZOJ2924 [Poi1998]Flat broken lines 【Dilworth定理 + 树状数组】
下一篇:全面认识JUnit 4的新特征

发表评论

最新留言

不错!
[***.249.68.78]2022年04月16日 08时23分44秒