题解 P4381 【[IOI2008]Island】

ywy_c_asm · 2018-10-25 22:02:43 · 题解

首先这是在一个固定长度的决策区间内最大化这个式子的值，然后这个式子可以写成(dp[a[i]]-dis[i])+(dp[a[j]]-dis[j])的形式，前者只和i有关，后者只和j有关，这是单调队列的套路，维护一下max\{dp[a[j]]-dis[j]\}就行了。

以上就是大致思路，还是不难的，可以发现这题就是由一堆套路拼成的。不过基环树这玩意我觉得代码写起来还是不那么容易，下面说一下实现的一些细节：

1.我们用一个邻接表配合并查集存每个基环树的所有点，这样省的每次都暴力找点（开100万个vector会炸……）

2.关于找环的问题，我们可以把这个基环树的树的部分删掉，就是考虑到每个叶子的度数都是1，就可以用类似拓扑排序的方法删点，当这个点的度数为1也就是说他没有前驱了就可以把他删掉加到队列里，注意这个跟拓扑排序不一样的地方是别忘了这是无向图，在遍历这个点的出边的时候别忘了排除已经删过的点。

3.把这个环转化成序列，就是先找一个环上的点，然后把他加入队列进行bfs（其实这是在环上并没必要用bfs，但是感觉比较好写），我们对每个环上的点维护一个nxt[i]表示他指向下一个点的边权是啥，注意别通过反向边走回去了。不过这里有个比较恶心的地方就是最后一个点，我们需要判一下他指向第一个点的边然后退出bfs，所以我们的vis标记需要标记在边上，这个可以用网络流里那种反向边^1的方法来标记边，然后把队列里的点复制一份接到后面就行了。

4.为防止爆栈要用bfs进行树形dp……

上代码~

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
inline int get(){//快读 
    int n=0;char c;
    while((c=getchar())||23333){
        if(c>='0'&&c<='9')break;
        if(c=='-')goto s;
    }
    n=c-'0';
    while((c=getchar())||23333){
        if(c>='0'&&c<='9')n=n*10+c-'0';
        else return(n);
    }
    s:while((c=getchar())||23333){
        if(c>='0'&&c<='9')n=n*10-c+'0';
        else return(n);
    }
}typedef struct _b{//边 
    int dest;int nxt;int len;unsigned char vis;//标记 
}bian;
bian memchi[2000001];
int gn=2;
int heads[1000001];
ll dp[1000001];
ll maxn=0;
int que[2001001];//队列 
inline void add(int s,int t,int l){
    memchi[gn].dest=t;
    memchi[gn].len=l;
    memchi[gn].nxt=heads[s];
    heads[s]=gn;gn++;
}
int nxts[1000001],fheads[1000001];//用来给基环树存点的邻接表 
int ints[1000001],deg[1000001];//并查集与度数数组 
unsigned char nohuan[1000001];//是否不在环上 
int find(int n){
    if(ints[n]==n)return(n);
    return(ints[n]=find(ints[n]));
}
int fa[1000001];//树形dp的时候维护父亲 
int nxt[1000001];//环上的点的出边的边权 
int xulie[2001001];//环转化成的序列 
unsigned char bv[1000001];
ll dis[2001001];
inline void tree_dp(int pt){//bfs树形dp 
    register int head=0,tail=1;que[0]=pt;do{
        int me=que[head];head++;
        for(register int i=heads[me];i;i=memchi[i].nxt){
            if(memchi[i].dest==fa[me]||!nohuan[memchi[i].dest])continue;
            fa[memchi[i].dest]=me;
            que[tail]=memchi[i].dest;
            tail++;
        }
    }while(head<tail);
    for(register int a=tail-1;a>=0;a--){//把队列里的点倒过来就能按顺序了 
        int me=que[a];
        for(register int i=heads[me];i;i=memchi[i].nxt){
            if(memchi[i].dest==fa[me]||!nohuan[memchi[i].dest])continue;
            ll p=dp[memchi[i].dest]+memchi[i].len;
            maxn=max(maxn,p+dp[me]);
            dp[me]=max(dp[me],p);
        }
    }
}
inline ll solve(int jh){//求基环树的最长链 
    register int head=0,tail=0;
    for(register int i=fheads[jh];i;i=nxts[i]){
        if(deg[i]==1)que[tail]=i,tail++,bv[i]=1;
    }
    while(head<tail){//对叶子进行“拓扑排序”只保留环 
        int me=que[head];head++;
        nohuan[me]=1;
        for(register int i=heads[me];i;i=memchi[i].nxt){
            if(bv[memchi[i].dest])continue;
            deg[memchi[i].dest]--;
            if(deg[memchi[i].dest]==1){
                que[tail]=memchi[i].dest;
                tail++;
                bv[memchi[i].dest]=1;
            }
        }
    }
    ll ans=0;
    int st;//环上第一个点 
    int cnt=0;
    for(register int i=fheads[jh];i;i=nxts[i]){
        if(!nohuan[i]){st=i;cnt++;
            maxn=0;
            tree_dp(i);
            ans=max(ans,maxn);
            ans=max(ans,dp[i]);
        }
    }
    bv[st]=1;
    head=0,tail=1;
    que[0]=st;
    int rcnt=cnt;//环长 
    do{//把这个环转化成序列 
        int me=que[head];
        head++;
        cnt--;
        for(register int i=heads[me];i;i=memchi[i].nxt){
            if(nohuan[memchi[i].dest])continue;
            if(memchi[i^1].vis)continue;//对走过的边进行标记 
            if(memchi[i].dest==st){//注意特判最后一个点 
                nxt[me]=memchi[i].len;break;
            }
            bv[memchi[i].dest]=1;
            nxt[me]=memchi[i].len;
            memchi[i].vis=1;
            que[tail]=memchi[i].dest;
            tail++;
            break;
        }
    }while(head<tail);
    int ptr=1;
    for(register int i=0;i<tail;i++){
        xulie[ptr]=que[i];ptr++;
    }
    for(register int i=0;i<tail;i++){//复制一份接到后面 
        xulie[ptr]=que[i];ptr++;
    }
    ptr--;
    for(register int i=2;i<=ptr;i++)dis[i]=dis[i-1]+nxt[xulie[i-1]];//前缀和 
    head=0,tail=0;
    for(register int i=1;i<=ptr;i++){//这个再普通不过的单调队列优化dp无需多解释了吧 
        while(head<tail&&i-que[head]>=rcnt)head++;
        if(head<tail){
            ans=max(ans,dis[i]+dp[xulie[i]]-dis[que[head]]+dp[xulie[que[head]]]);
        }
        while(head<tail&&dp[xulie[que[tail-1]]]-dis[que[tail-1]]<=dp[xulie[i]]-dis[i])tail--;
        que[tail]=i;tail++;
    }
    return(ans);
}
signed main(){
    int n;
    n=get();
    for(register int i=1;i<=n;i++)ints[i]=i;
    ll tot=0;
    for(register int i=1;i<=n;i++){
        int t=get(),l=get();
        add(i,t,l);
        add(t,i,l);
        deg[i]++;
        deg[t]++;
        tot+=l;
        int aa=find(i),ab=find(t);
        if(aa!=ab){
            ints[aa]=ab;
        }
    }
    ll ans=0;
    for(register int i=1;i<=n;i++){
        int aa=find(i);
        nxts[i]=fheads[aa];//使用邻接表向基环树里存点 
        fheads[aa]=i;
    }
    for(register int i=1;i<=n;i++){
        if(ints[i]==i)ans+=solve(i);//统计答案 
    }
    cout<<ans<<endl;
    return(0);
}