CF1970G2 Min-Fund Prison (Medium) 题解

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

。

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

若连向第二个联通块，则

dp_{i,j,0}\mid=dp_{i-1,j,0}

dp_{i,j,1}\mid=dp_{i-1,j,1}

若连向第一个联通块，则

dp_{i,j,0}\mid=dp_{i-1,j-siz_{rt},0}

dp_{i,j,1}\mid=dp_{i-1,j-siz_{rt},1}

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

dp_{i,j,0}\mid=dp_{i-1,j-(siz_{rt}-siz_{x}),0}

dp_{i,j,1}\mid=dp_{i-1,j-siz_{x},1}

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

Code :

CPP

#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;
	}
}

CF1970G2 Min-Fund Prison (Medium) 题解

文章操作

Before it ：

Solution ：

Code :

相关推荐

评论

CF1970G2 Min-Fund Prison (Medium) 题解