基环树

ooliver 发布于 15 小时前 38 次阅读 OI

AI 摘要

基环树破解“墙上的舞者”困境！只需找到环、断开一条边，再用DP两端分别跑两次取最优。环上还能贪心回溯：下一点大于回溯点？果断断开！

基环树

P2607 [ZJOI2008] 骑士

没有上司的舞会的加强版，找到基环树的环之后断开一条边，以断边的两个端点为根 dp 即可，注意原图可能是森林。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e6+5;
struct edge{int v,id;};
vector<edge> g[N];
int n,ans,r1,r2,E,a[N],v[N],dp[N][2];

void find(int u,int p){
    v[u]=1;
    for(auto e:g[u]){
        if(e.id==(p^1))continue;
        if(v[e.v]){
            if(!E){r1=u,r2=e.v,E=e.id;}
            continue;
        }
        find(e.v,e.id);
    }
}

void dfs(int u,int p){
    dp[u][0]=0,dp[u][1]=a[u];
    for(auto e:g[u]){
        if(e.id==p||e.id==(p^1)||e.id==E||e.id==(E^1))continue;
        dfs(e.v,e.id);
        dp[u][0]+=max(dp[e.v][0],dp[e.v][1]);
        dp[u][1]+=dp[e.v][0];
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1,w,u,tot=1;i<=n;i++){
        cin>>w>>u;
        a[i]=w;
        g[i].push_back({u,++tot});
        g[u].push_back({i,++tot});
    }
    for(int i=1;i<=n;i++) if(!v[i]){
        E=0;
        find(i,-1);
        dfs(r1,0);int t=dp[r1][0];
        dfs(r2,0);ans+=max(t,dp[r2][0]);
    }
    cout<<ans;
    return 0;
}

P5022 [NOIP 2018 提高组] 旅行 + P5049 [NOIP 2018 提高组] 旅行 加强版

直接按照加强版的数据来做。

对于 $m=n-1$ 的情况，直接将子节点排序再 DFS 即可。

对于 $m=n$，也就是基环树的情况，我们考虑先找出环。当从根节点出发，走到环上。当我们在环上使用回溯时，就相当于断开了当前点到回溯点的那条边、之后就可以按照树的方法来做。考虑贪心在什么情况下回溯：当环上下一个点比回溯后能访问的点要大时，选择回溯。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int n,m,tag,h[N],vis[N],f[N];
vector<int> t[N];

void dfs(int u,int fa){
    cout<<u<<" ";
    for(int v:t[u]) if(v!=fa) dfs(v,u);
}

void dfs1(int u,int fa){
    vis[u]=1,f[u]=fa;
    for(int v:t[u]){
        if(v==fa) continue;
        if(vis[v]){
            if(!tag){
                tag=1,h[v]=1;
                int x=u;
                while(x!=v) h[x]=1,x=f[x];
            }
        }
        else dfs1(v,u);
    }
}

void dfs2(int u,int b){
    vis[u]=1;
    cout<<u<<" ";
    for(int i=0;i<t[u].size();i++){
        int v=t[u][i];
        if(vis[v]) continue;
        int nxt=0;
        for(int j=i+1;j<(int)t[u].size();j++) if(!vis[t[u][j]]){
            nxt=t[u][j];
            break;
        }
        if(h[u]&&h[v]&&!tag){
            if(v>(nxt?nxt:b)){
                tag=1;
                continue;
            }
        }
        dfs2(v,nxt?nxt:b);
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        t[u].push_back(v);
        t[v].push_back(u);
    }
    for(int i=1;i<=n;i++) sort(t[i].begin(),t[i].end());
    if(m==n-1){
        dfs(1,-1);
        return 0;
    }
    dfs1(1,-1);
    tag=0;
    memset(vis,0,sizeof vis);
    dfs2(1,1e9);
    return 0;
}