CF2127 H O(n) 做法

_Ch1F4N_ · 2025-08-08 13:00:57 · 题解

注意到一个 K_4 中一个点恰好有 6 个经过其的简单环，所以原图一定是广义串并联图，所以建出这个图的 Top tree 然后对于每个簇记录 dp_{0/1/2,0/1/2} 表示考虑簇内的边时在上下界点已经被覆盖了多少次的情况下最多能在簇内选出多少条边，合并的时候直接类似背包地暴力合并即可，时间复杂度 O(n+m)，由于广义串并联图上 n,m 同级所以其实是 O(n) 的。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+114;
unordered_map<int,int> e[maxn],f[maxn][3][3];
unordered_set<int> E[maxn];
int n,m;
queue<int> q;
int ans;
void work(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        if(e[min(u,v)][max(u,v)]==0){
            e[min(u,v)][max(u,v)]=1;
            E[u].insert(v);
            E[v].insert(u);
            f[u][1][1][v]=1;
            f[v][1][1][u]=1;
        }else{
            f[u][2][2][v]=2;
            f[v][2][2][u]=2;
        }
    }
    for(int i=1;i<=n;i++) if(E[i].size()<=2) q.push(i);
    while(q.size()>0){
        int u=q.front();
        q.pop();
        if(E[u].size()==1){
            int v=(*E[u].begin());
            if(E[v].size()==1) break;
            int w=(*E[v].begin());
            E[u].erase(v);
            E[v].erase(u);
            if(w==u) w=(*E[v].begin());
            e[min(u,v)][max(u,v)]=0;
            //f[min(u,v)][max(u,v)] 合并到 f[min(w,v)][max(w,v)] 上
            int dp[3][3];
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++) dp[i][j]=0;
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++){
                    for(int k=0;k<3;k++){
                        for(int l=0;l<3;l++){
                            //u,v v,w
                            if(j+k<3){
                                dp[j+k][l]=max(dp[j+k][l],f[u][i][j][v]+f[v][k][l][w]);
                            }
                        }
                    }
                }
            }
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++) f[v][i][j][w]=dp[i][j],f[w][j][i][v]=dp[i][j];
            }
            if(E[v].size()<=2) q.push(v);
        }else if(E[u].size()==2){
            int x=(*E[u].begin());
            E[u].erase(x);
            E[x].erase(u);
            int y=(*E[u].begin());
            E[u].erase(y);
            E[y].erase(u);
            int dp[3][3];
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++) dp[i][j]=0;
            }
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++){
                    for(int k=0;k<3;k++){
                        for(int l=0;l<3;l++){
                            //x,u u,y
                            if(j+k<3) dp[i][l]=max(dp[i][l],f[x][i][j][u]+f[u][k][l][y]);
                        }
                    }
                }
            }
            if(e[min(x,y)][max(x,y)]==0){
                e[min(x,y)][max(x,y)]=1;
                E[x].insert(y);
                E[y].insert(x);
                for(int i=0;i<3;i++){
                    for(int j=0;j<3;j++) f[x][i][j][y]=dp[i][j],f[y][j][i][x]=dp[i][j];
                }
            }else{
                int g[3][3];
                for(int i=0;i<3;i++){
                    for(int j=0;j<3;j++){
                        g[i][j]=0;
                    }
                }
                for(int i=0;i<3;i++){
                    for(int j=0;j<3;j++){
                        for(int k=0;k<3;k++){
                            for(int l=0;l<3;l++){
                                //x,y
                                if(i+k<3&&j+l<3){
                                    g[i+k][j+l]=max(g[i+k][j+l],f[x][i][j][y]+dp[k][l]);
                                }
                            }
                        }
                    }
                }
                for(int i=0;i<3;i++){
                    for(int j=0;j<3;j++) f[x][i][j][y]=g[i][j],f[y][j][i][x]=g[i][j];
                }
            }
            if(E[x].size()<=2) q.push(x);
            if(E[y].size()<=2) q.push(y);
        }
    }
    for(int u=1;u<=n;u++){
        if(E[u].size()>=1){
            int v=(*E[u].begin());
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++) ans=max(ans,f[u][i][j][v]);
        }
    }
    cout<<ans<<"\n";
    for(int i=1;i<=n;i++){
        e[i].clear();
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++) f[i][j][k].clear();
        E[i].clear();
    }
    ans=0;
    while(q.size()>0) q.pop();
    return ;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--) work();
    return 0;
}