题解 P2538 [SCOI2008]城堡

vectorwyx · 2022-12-24 13:01:05 · 题解

题意：给定一棵基环树森林，起初有 m 个点已被选进 S 里，你需要再选 k 个点加入到 S 中，最小化其余点到 S 距离的最大值。

二分，树的部分同 P3523 做 dp。但是根结点（也就是在环上的点）的处理要保留，如果当前子树中最深的还未被覆盖的点距离根结点的距离为 d，它要求环上的某段区间 [l,r] 里至少有一个点被选进 S 里，然后最小化环上被选进 S 的点数。这个问题和 P4155 的形式是一致的，断环成链后变为经典贪心，每次从还未被满足的区间中选一个右端点最靠左的区间，把它的右端点选进 S 里。复杂度 O(n^2\log n)，通过倍增应该能优化到 O(n\log^2 n)，但是懒得写了。

代码如下：

#include<bits/stdc++.h>
namespace vectorwyx{
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define uint unsigned
#define ull unsigned long long
#define umap unordered_map
#define db double
#define fo(i,x,y) for(int i=(x);i<=(y);++i)
#define go(i,x,y) for(int i=(x);i>=(y);--i)
#define ptc putchar
#define emp emplace
#define re return
#define co continue
#define brk break
#define HH (ptc('\n'))
#define bctz __builtin_ctz
#define bclz __builtin_clz
#define bppc __builtin_popcount
using namespace std;
ll seed=chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
inline int rm(int x,int y){return (int)(rnd()%(y-x+1ll)+x);}
inline int read(){signed ch=getchar();int x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void out(int *a,int l,int r){fo(i,l,r) cout<<*(a+i)<<' ';puts("");}

//8:36~9:44~
const int N=105,inf=1e9;
int a[N],num,n,m,k,vis[N],ti,f[N],g[N],stk[N],top,ins[N],rk[N];
int mp[N][N];
vector<pii> e[N];

void dfs1(int x){
    if(vis[x]==ti) re;
    vis[x]=ti;
    for(auto i:e[x]) dfs1(i.fi);
}

struct Ctree{
int cir[N],ct,rvl[N],k,ins[N],ans,l[N],r[N],m,fl,nxt[N],sum[N],R[N];

void insert(int x){
    cir[++ct]=x;
    rk[x]=ct;ins[x]=1;
}
void play_it(){
    fo(i,1,ct-1) rvl[i]=rvl[i+ct]=mp[cir[i]][cir[i+1]];
    rvl[ct]=mp[cir[ct]][cir[1]];
    fo(i,1,ct) if(a[cir[i]]){fl=i;brk;}
    fo(i,1,2*ct-1) sum[i+1]=sum[i]+rvl[i];
//  cout<<"rvl:";out(rvl,1,2*ct);cout<<"sum:";out(sum,1,2*ct);
}

void dfs(int x,int fa){
    f[x]=0,g[x]=inf;
    for(auto i:e[x]) if(!ins[i.fi]&&i.fi!=fa){
        dfs(i.fi,x);
        big(f[x],f[i.fi]+i.se);
        sml(g[x],g[i.fi]+i.se);
    }
    if(a[x]) g[x]=0;
    if(f[x]+g[x]<=k) f[x]=-inf;
    if(f[x]+mp[x][fa]>k) f[x]=-inf,g[x]=0,ans++;//,printf("%d!\n",x); 
}

int solve(){
//  printf("solve(%d)\n",k);
    ans=m=0;
    fo(i,1,ct)
        dfs(cir[i],0);
//  printf("now ans=%d!\n",ans);
//  fo(i,1,ct) printf("%d:(%d,%d)\n",i,f[cir[i]],g[cir[i]]);
    int Fl=0;
    fo(i,1,2*ct) R[i]=inf;
    fo(i,1,ct){
        bool flg=0;
        fo(j,1,ct){
            int dis=abs(sum[i]-sum[j]);sml(dis,sum[ct+1]-dis);
            if(f[cir[i]]+g[cir[j]]+dis<=k){flg=1;brk;}
        }
        if(flg) co;
        int len=k-f[cir[i]];
//      printf("%d:len=%d\n",i,len);
        if(2*len>=sum[ct+1]){
//          puts("qwq");
            if(!fl) Fl=1;
            co;
        }
        ++m;
        if(sum[i]+rvl[ct]>len){
            l[m]=1;r[m]=2*ct;
            go(j,i,1) if(sum[i]-sum[j]>len){l[m]=j+1;brk;}
            fo(j,i,2*ct) if(sum[j]-sum[i]>len){r[m]=j-1;brk;}
            if(r[m]>ct) co;
            l[m+1]=l[m]+ct;r[m+1]=r[m]+ct;
            ++m;
        }else{
            l[m]=1;r[m]=2*ct;
            go(j,i+ct,1) if(sum[i+ct]-sum[j]>len){l[m]=j+1;brk;}
            fo(j,i+ct,2*ct) if(sum[j]-sum[i+ct]>len){r[m]=j-1;brk;}         
        }
    }
    if(!m) re ans+Fl;
//  fo(i,1,m) printf("[%d,%d]\n",l[i],r[i]);
    fo(i,1,m) sml(R[l[i]],r[i]);
    int c=0,mn=inf;
    go(i,2*ct,1){
        nxt[i]=mn;
        sml(mn,R[i]);
    }
    if(fl){
        int x=fl;
        while(nxt[x]<fl+ct){
            c++;
            x=nxt[x];
        }
    }else{
        c=inf;
        fo(i,1,ct){
            int x=i,rp=1;
            while(nxt[x]<i+ct){
                rp++;
                x=nxt[x];
            }
            sml(c,rp);
        }
    }
    big(c,Fl);
    re ans+c;
}
}tr[N];

bool dfs2(int x,int fa){
    stk[++top]=x;vis[x]=ti;
    bool fl=0;
    for(auto i:e[x]){
        if(vis[i.fi]==ti){//基环树找环一定要特判父亲！！
            if(i.fi==fa){
                if(!fl){
                    fl=1;
                    co;
                }   
            }
            do{
                tr[num].insert(stk[top]);
            }while(stk[top--]!=i.fi);
            re 1;
        }
        if(dfs2(i.fi,x)) re 1;
    }
    top--;
    re 0;
}

signed main(){
    cin>>n;int w=read();cin>>m;
    {
    int x[N];fo(i,1,n) x[i]=read()+1;
    fo(i,1,n) fo(j,1,n) mp[i][j]=inf;
    fo(i,1,n){
        int v=read();
        e[i].eb(x[i],v);
        e[x[i]].eb(i,v);
//      printf("%d <-> %d %d\n",i,x[i],v);
        sml(mp[i][x[i]],v);
        sml(mp[x[i]][i],v);
    }       
    }

    fo(i,1,w) a[read()+1]=1;
    fo(i,1,n) if(!vis[i]){
        ++ti;++num;
        dfs1(i);
        ++ti;
        dfs2(i,0);
        tr[num].play_it();
//      tr[i].rvl[tr[i].ct]=mp[tr[i]]
    }
//  tr[1].k=5;cout<<tr[1].solve()<<'\n';
//  tr[2].k=3;cout<<tr[2].solve()<<'\n';
//  re 0;
    int l=0,r=inf,mid,ans=inf;
    while(l<=r){
        mid=(l+r)>>1;
        int x=0;
        fo(i,1,num) tr[i].k=mid,x+=tr[i].solve();
        if(x>m) l=mid+1;
        else r=mid-1,ans=mid;
    }
    cout<<ans;
    return 0;
}
}
/*
-------------------------------------------------
*/

signed main(){re vectorwyx::main();}