题目传送门

代码：

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){

   	int s=0;

   	int w=1;

   	char ch=getchar();

   	for(;ch<'0'||ch>'9';ch=getchar())

    	if(ch=='-')

			w=-1;

   	for(;ch>='0'&&ch<='9';ch=getchar())

		s=s*10+ch-'0';

   	return s*w;

}

int n,m,k;

int cnt;

int dp[100086];

int f[100086];

int p[100086];

int s[100086];

int find(int u){
	
	if(f[u]==u)
	
		return u;
		
	return f[u]=find(f[u]);
	
}

signed main(){

	n=read();
	
	m=read();
	
	k=read();
	
	if(k==0&&n>=m){
	
		cout<<m<<"\n";
	
		exit(0); 
	
	}
	
	for(int i=1;i<=n;i++){
		
		f[i]=i;
		
		p[i]=1;
		
	}
	dp[0]=1;
	
	for(int i=1;i<=k;i++){
		
		int x=read();
		
		int y=read();
		
		int u=find(x);
		
		int v=find(y);
		
		if(u!=v){
			
			f[u]=v;
			
			p[v]+=p[u];
			
		}
		
	}
	
	for(int i=1;i<=n;i++)
	
		if(f[i]==i)
		
			s[++cnt]=p[i];
			  			
	for(int i=1;i<=cnt;i++)
	
		for(int j=2*m;j>=s[i];j--)
		
			dp[j]=max(dp[j],dp[j-s[i]]+s[i]);
			
	long long minn=999999999;
	
	long long ans=999999999;
			
	for(int i=1;i<=2*m;i++)
	
		if(minn>abs(dp[i]-m)){
			
			minn=abs(dp[i]-m),ans=dp[i];
		
		}
		
	if(ans==999999999){
	
		cout<<0;
		
		exit(0);
		
	}
	
	cout<<ans;

	return 0;
	
}

测评记录