CF1970G3题解

EXODUS · 2024-05-26 20:18:25 · 题解

Part 1：前言

Wrong Answer on test 10！Wrong Answer on test 11！

upd on 2024.6.6：G2 特化代码贴错了，进行了修改。

Part 2：正文

先来考虑树的部分，注意到全图联通，所以多连边是没有用的，我们只需要枚举在哪条边断掉即可。预处理每个点子树和子树补的大小即可做到时间复杂度 O(n)。

然后考虑图的部分。注意到如果我们选择断掉连通块里的边，则断掉的边一定是桥，否则断掉后不符合题意，同时，我们加边的目的也只会是把不连通的连通块连接起来，否则会减少桥的个数，一定不优。

基于以上分析，不难写出一个 dp。令 f(i,j) 表示考虑到第 i 个连通块，最终答案中某一个连通块的大小是 j 是否可行。同时令 g(i,j) 表示在不断边的情况下，前面的连通块是否可以构成一个大小为 j 的连通块。枚举到一个连通块时，先求出这个连通块所有边双，缩掉边双成树后，统计树上每个点子树的大小。此时树上的每条边都是桥。如果当前选择断掉树上的边，设断掉后树两侧的节点树分别为 v_1,v_2，则有转移 f(i,j)\leftarrow g(i-1,j-v_1),f(i,j)\leftarrow g(i-1,j-v_2)，对 g(i,j) 则有转移 g(i,j)\leftarrow g(i-1,j-S)，其中 S 为连通块大小。最后在 f(c,*)=1 处贡献答案即可，c 为连通块个数。

直接 dp 即可做到 O(n^2)。注意到 f 和 g 均为 01，且转移形式简单，故可以 bitset 优化，做到 O\left(\dfrac{n^2}{\omega}\right)。

对于 G2 我们其实还有一个特化做法，枚举哪条边断掉，然后搜每个连通块的大小，直接对这个做背包，然后贡献到答案即可。注意到断掉非桥边一定不优于断掉连通块中的桥边，也不优于不断边，故可以保证正确性。时间复杂度 O(n^2m) 到 O\left(\dfrac{n^2m}{\omega}\right) 不等。

Part 3：代码

G2 特化做法

// You don't have to be sorry
// 你也无需抱有歉意
// I don't have to be brave
// 而我也不必鼓起勇气
// I'm picking up where I started
// 我在重新拾起初忆
// And I'mma make it okay
// 我将会让一切回到正轨
// Leave the keys to my apartment
// 你走吧，不过记得把钥匙给我
// Cause I don't need you to stay
// 因为我并不需要你的留下
// Yeah you don't have to be sorry
// 没错，你无需抱有歉意
// And I'mma make it okay
// 我现在过得很是滋润
// Cause you make me better
// 都是你拜你所赐

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

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;

#define rep(i,l,r) for(int i(l);i<=(r);++i)
#define per(i,r,l) for(int i(r);i>=(l);--i)
#define eb emplace_back
#define File(filename) freopen(filename ".in","r",stdin),freopen(filename ".out","w",stdout)
#define Exit(p) fprintf(stderr,"[exit]: at breakpoint %d\n",p),exit(0);

#ifdef EXODUS
    #define Debug(...) fprintf(stderr,__VA_ARGS__)
#else
    #define Debug(...) 0
#endif

//=========================================================================================================
// Something about IO

template<typename T>
void read(T &x){
    x=0;T flg=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')flg=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    x*=flg;
}
template<typename T>
void seq_read(T bg,T ed){for(auto i=bg;i!=ed;++i)read(*i);}
template<typename T,typename... Args>
void read(T &x,Args &...args){read(x),read(args...);}

//=========================================================================================================
//Some useful function

template<typename T>
void cmax(T& x,T y){x=max(x,y);}
template<typename T,typename... Args>
void cmax(T& x,T y,Args ...args){cmax(x,y);cmax(x,args...);}
template<typename T>
void cmin(T& x,T y){x=min(x,y);}
template<typename T,typename... Args>
void cmin(T& x,T y,Args ...args){cmin(x,y);cmin(x,args...);}
template<typename T,typename U>
void seq_assign(T bg,T ed,U val){for(auto i=bg;i!=ed;++i)(*i)=val;}
template<typename T,class F,class=enable_if_t<is_invocable_v<F>>>
void seq_assign(T bg,T ed,F func){for(auto i=bg;i!=ed;++i)(*i)=func(i);}
template<typename T>
void seq_copy(T dstbg,T dsted,T srcbg,T srced){for(auto i=dstbg,j=srcbg;i!=dsted&&j!=srced;++i,++j)(*i)=(*j);}

//=========================================================================================================
// Define the global variables here.

bool membg=0;

constexpr int N=3e5+7;
constexpr ll inf=LONG_LONG_MAX;
int n,m,c;
vector<int>g[N];
int low[N],dfn[N],siz[N],dfx;
bitset<N>F,G,H;

bool memed=0;

//=========================================================================================================
// Code here.

void solve(){
    read(n,m,c);
    for(int i=1;i<=n;i++)
        g[i].clear(),dfn[i]=low[i]=0;
    dfx=0;
    F.reset(),G.reset();
    for(int i=1;i<=m;i++){
        int u,v;read(u,v);
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<int>lis;
    auto tarjan=[&](auto self,int u,int fa)-> void {
        siz[u]=1;dfn[u]=low[u]=++dfx;
        for(auto v:g[u])
            if(!dfn[v])
                self(self,v,u),low[u]=min(low[u],low[v]),siz[u]+=siz[v];
            else if(v!=fa)
                low[u]=min(low[u],dfn[v]);
        if(dfn[u]==low[u])
            lis.emplace_back(siz[u]);
    };
    F.set(0);G.set(0);
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(!dfn[i]){
            ++cnt;
            lis.clear();
            tarjan(tarjan,i,0);
            lis.pop_back();
            // printf("> ");
            // for(auto v:lis)
            //  printf("%d ",v);
            // printf("\n");
            for(auto v:lis)
                F|=G<<v,F|=G<<(siz[i]-v);
            G|=G<<siz[i];
        }
    F|=G;
    ll ans=inf;
    for(int i=1;i<n;i++)
        if(F.test(i))
            ans=min(ans,(ll)(cnt-1)*c+(ll)i*i+(ll)(n-i)*(n-i));
    printf("%lld\n",ans==inf?-1ll:ans);
    return;
}

//=========================================================================================================

int main(){
    Debug("%.3lfMB\n",fabs(&memed-&membg)/1024.0/1024.0);
    int timbg=clock();
    int T=1;read(T);
    while(T--)solve();
    int timed=clock();
    Debug("%.3lfs\n",1.0*(timed-timbg)/CLOCKS_PER_SEC);
    fflush(stdout);
    return 0;
}