qwq
  • 板块P2170 选学霸
  • 楼主dtrthg
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/7/28 22:59
  • 上次更新2023/10/27 17:56:21
查看原帖
qwq
379113
dtrthg楼主2022/7/28 22:59

这段die码为什么过不了啊啊啊啊啊啊啊啊啊啊啊啊啊

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
const int Maxn=2e4+10;
int dp[Maxn],fa[Maxn];
int data[Maxn],a[Maxn];
int find(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
int main()
{
	int n,m,k;cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		fa[i]=i;	
	}
	memset(data,1,sizeof(data));
    //init
    while(k--)
    {
    	int x,y;cin>>x>>y;
    	int faX=find(x),faY=find(y);
    	fa[faY]=faX;
    	if(faX!=faY) 
		{
			fa[faY]=faX;
			data[faX]+=data[faY];
		}
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(fa[i]==i)
		{
			a[++cnt]=data[i];
		}
	}
    //并查集处理
    for(int i=1;i<=cnt;i++)
    {
    	for(int j=n;j>=a[i];j--)
    	{
    		dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
		}
	}
    //dp
    int ans=INF,x=INF;
    for(int i=1;i<=n;i++)
    {
    	if(x>abs(dp[i]-m))
		{
			x=abs(dp[i]-m);
			ans=dp[i];
		} 
	}
	if(ans==INF) cout<<'0'<<endl; 
	else cout<<ans<<endl;
    //out
    return 0;
}
/*
in1:
4 3 2
1 2
3 4
out1:
2
*/

2022/7/28 22:59
加载中...