dp训练记录 2025.1

猿柒

8个月前更新

Min-Fund Prison (Medium)

https://www.gxyzoj.com/d/hzoj/p/CF1970G2

显然，要加的边数就是联通快的个数-1，所以只需要让x,y尽量接近即可

因为要分成两个联通快，所以删掉的边一定是割边或加上的边

有一个性质，经过边双缩点后的图一定是一个森林，记深度较大的节点为u，x子树大小为\(siz_x\)，所以断开割边后的两部分的值分别为\(siz_u\)和\(siz_rt-siz_u\)

考虑dp，因为算平方很难统计，考虑可行性dp

设\(dp_{i,j,0/1}\)表示当前是第i个联通快，第一个联通快大小为j，是否断开已知边

显然的，如果没有断开，直接连到对应联通快即可，有：

\(dp_{i,j,0}|=dp_{i-1,j,0}\)

\(dp_{i,j,0}|=dp_{i-1,j-siz_rt,0}\)

\(dp_{i,j,1}|=dp_{i-1,j,1}\)

\(dp_{i,j,1}|=dp_{i-1,j-siz_rt,1}\)

对于断开已知边，必然会分成两部分，一部分连在第一个联通快，另一部分在第二个

\(dp_{i,j,1}|=dp_{i-1,j-(siz_rt-siz_x),0}\)

\(dp_{i,j,1}|=dp_{i-1,j-siz_x,0}\)

最后看每一个j值是否可行即可

初始状态为\(dp_{0,0,0}=1\)

点击查看代码

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
int n,m,T,head[305],edgenum,head1[305],edgenum1,cnt;
ll c;
struct edge{
	int to,nxt;
}e[606],e1[606];
void add_edge(int u,int v)
{
	e[++edgenum].nxt=head[u];
	e[edgenum].to=v;
	head[u]=edgenum;
}
void add_edge1(int u,int v)
{
	e1[++edgenum1].nxt=head1[u];
	e1[edgenum1].to=v;
	head1[u]=edgenum1;
}
int s[305],dfn[305],low[305],idx,top,ecnt,id[305],siz[305];
bool bri[305];
void tarjan(int i,int in_edge)
{
	dfn[i]=low[i]=++idx;
	s[++top]=i;
	for(int u=head[i];u;u=e[u].nxt)
	{
		int j=e[u].to;
		if(!dfn[j])
		{
			tarjan(j,u);
			low[i]=min(low[i],low[j]);
			if(low[j]>dfn[i])
			{
				bri[u]=bri[u^1]=1;
			}
		}
		else if(u!=(in_edge^1))
		{
			low[i]=min(low[i],dfn[j]);
		}
	}
	if(dfn[i]==low[i])
	{
		ecnt++;
		int v=0;
		while(v!=i)
		{
			v=s[top];
			top--;
			id[v]=ecnt;
			siz[ecnt]++;
		}
	}
}
int rt[305],st[305];
bool vis[305],dp[305][305][2];
void dfs(int u,int root)
{
	vis[u]=1;
	rt[u]=root;
	for(int i=head1[u];i;i=e1[i].nxt)
	{
		int v=e1[i].to;
		if(vis[v]) continue;
		dfs(v,root);
//		printf("%d %d %d %d\n",u,v,siz[u],siz[v]);
		siz[u]+=siz[v];
	}
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%lld",&n,&m,&c);
		for(int i=1;i<=n;i++)
		{
			head[i]=head1[i]=dfn[i]=low[i]=0;
			siz[i]=vis[i]=bri[i]=0;
		}
		top=cnt=idx=ecnt=0;
		edgenum=1,edgenum1=0;
		for(int i=1;i<=m;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			add_edge(u,v);
			add_edge(v,u);
		}
		for(int i=1;i<=n;i++)
		{
			if(!dfn[i])
			{
				tarjan(i,0);
			}
		}
		for(int i=1;i<=n;i++)
		{
//			printf("%d ",id[i]);
			for(int j=head[i];j;j=e[j].nxt)
			{
				int v=e[j].to;
				if(id[i]!=id[v])
				{
//					printf("%d %d\n",i,v);
					add_edge1(id[i],id[v]);
				}
			}
		}
		if(ecnt==1)
		{
			printf("-1\n");
			continue;
		}
		cnt=0;
//		for(int i=1;i<=ecnt;i++)
//		{
//			printf("%d ",siz[i]);
//		}
		for(int i=1;i<=ecnt;i++)
		{
			if(!vis[i])
			{
				dfs(i,i);
				st[++cnt]=i;
			}
		}
//		printf("%d\n",ecnt);
		for(int i=1;i<=cnt;i++)
		{
			for(int j=0;j<=n;j++)
			{
				dp[i][j][0]=dp[i][j][1]=0;
			}
		}
		dp[0][0][0]=1;
		c=(cnt-1)*c;
		for(int i=1;i<=cnt;i++)
		{
//			printf("%d ",st[i]);
			int srt=siz[st[i]];
			for(int j=0;j<=n;j++)
			{
				if(j>=srt)
				{
					dp[i][j][0]|=dp[i-1][j-srt][0];
					dp[i][j][1]|=dp[i-1][j-srt][1];
				}
				dp[i][j][0]|=dp[i-1][j][0];
				dp[i][j][1]|=dp[i-1][j][1];
				for(int k=1;k<=ecnt;k++)
				{
					if(rt[k]!=st[i]||k==st[i]) continue;
					if(j>=srt-siz[k]) dp[i][j][1]|=dp[i-1][j-srt+siz[k]][0];
					if(j>=siz[k]) dp[i][j][1]|=dp[i-1][j-siz[k]][0];
				}
			}
		}
		ll 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));
//				printf("%d %d\n",dp[cnt][i][0],dp[cnt][i][1]);
			}
		}
		printf("%lld\n",ans+c);
	}
	return 0;
}

来源链接：https://www.cnblogs.com/wangsiqi2010916/p/18687699

评分

欢迎为Ta评分