CF1970G2 Min-Fund Prison (Medium) 题解

Aapwp_ · 2025-01-24 17:51:24 · 题解

Before it ：

感觉和树形 dp 没什么关系啊……

其次感谢 @wangsiqi2010916 大佬在此题上对我的思路和部分细节的指导！

Solution ：

容易发现，为了使整张图联通，我们需要添加的边数是一定的，为图上联通块的个数 -1。

所以原式中 k\times c 的值是不变的，我们只需要使 x^2+y^2 的值最小。有 x^2+y^2=(x+y) \times (x-y)，x+y 不变，为图的大小，所以我们只需要最小化 x 和 y 的差即可。

考虑对原图进行边双缩点，缩完点后得到的图一定是一个森林，记 x 所在的联通块大小为 siz_x，断开割边后两部分值一定是 siz_x 和 图的大小减去 siz_x。

考虑可行性 dp。设 dp_{i,j,0/1} 表示第 i 个联通块，其中一个联通块大小为 j，是否断边。dp 值为 1 表示可行，0 为不可行。初始时 dp_{0,0,0}=1。

接下来状态转移，如果没有断开，则直接连到对应联通块即可。

若连向第二个联通块，则

若连向第一个联通块，则

若断边，则必然会分成两部分，一部分在第一个联通块，将其更新，则有

注意这里使用或进行转移。

Code :

#include<bits/stdc++.h> 
#define int long long 
using namespace std;
const int maxn=305; 
int T,n,m,c;
struct edge{
    int to,nxt;
}e[2*maxn];
int head[maxn],edgenum=1;
void add_edge(int u,int v){
    e[++edgenum].nxt=head[u];
    e[edgenum].to=v;
    head[u]=edgenum;
}
int dp[maxn][maxn][3];

int dfn[maxn],low[maxn],tim,sum,siz[maxn],col[maxn];
stack<int> s;
void tarjan(int u,int fa){//边双缩点    
    dfn[u]=low[u]=++tim;
    s.push(u);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v,i);
            low[u]=min(low[u],low[v]); 
        }
        else if(i!=(fa^1)) low[u]=min(low[u],dfn[v]); 
    }
    if(low[u]==dfn[u]){
        sum++;
        int y;
        do{
            y=s.top();
            s.pop();
            siz[sum]++;
            col[y]=sum;
        }while(y!=u);
    }
}
vector<int> vec[maxn];
int rt[maxn],st[maxn];
bool vis[maxn];
void dfs(int u,int root){
    vis[u]=1;
    rt[u]=root;
    for(int v:vec[u]){
        if(vis[v]) continue;
        dfs(v,root);
        siz[u]+=siz[v];
    }
}
void clear(){
    memset(e,0,sizeof(e));
    memset(head,0,sizeof(head));
    memset(dfn,0,sizeof(dfn));
    memset(dp,0,sizeof(dp));
    memset(low,0,sizeof(low));
    memset(col,0,sizeof(col));
    memset(siz,0,sizeof(siz));
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++){
        for(int j=0;j<vec[i].size();j++) vec[i][j]=0;
    }
    tim=0,sum=0;
    edgenum=1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin>>T;
    while(T--){
        cin>>n>>m>>c;
        clear();
        for(int i=1,x,y;i<=m;i++){
            cin>>x>>y;
            add_edge(x,y);
            add_edge(y,x);
        }
        for(int i=1;i<=n;i++){
            if(!dfn[i]) tarjan(i,0);
        }
        if(sum==1){
            cout<<-1<<endl;
            continue;
        }
        for(int i=1;i<=n;i++){
            for(int j=head[i];j;j=e[j].nxt){
                if(col[e[j].to]!=col[i]){
                    vec[col[e[j].to]].push_back(col[i]);
                    vec[col[i]].push_back(col[e[j].to]);
                }
            }
        }
        int cnt=0;
        for(int i=1;i<=sum;i++){
            if(!vis[i]){
                dfs(i,i);
                st[++cnt]=i;//共有cnt棵树 
            }
        }
        dp[0][0][0]=1;
        c=(cnt-1)*c;
        for(int i=1;i<=cnt;i++){
            int tot=siz[st[i]];
            for(int j=0;j<=n;j++){//枚举大小 
                if(j>=tot){
                    dp[i][j][0]|=dp[i-1][j-tot][0];
                    dp[i][j][1]|=dp[i-1][j-tot][1];
                }
                dp[i][j][0]|=dp[i-1][j][0];
                dp[i][j][1]|=dp[i-1][j][1];
                for(int k=1;k<=sum;k++){
                    //k不属于第i块 
                    if(rt[k]!=st[i] || k==st[i]) continue;
                    if(j>=tot-siz[k]) dp[i][j][1]|=dp[i-1][j-tot+siz[k]][0];
                    if(j>=siz[k]) dp[i][j][1]|=dp[i-1][j-siz[k]][0];
                }
            }
        }
        long long ans=1e17;
        for(int i=0;i<=n;i++){
            if(dp[cnt][i][0] || dp[cnt][i][1]){
                ans=min(ans,1ll*i*i+1ll*(n-i)*(n-i));
            }
        }
        cout<<ans+c<<endl;
    }
}