81pts 求调
  • 板块P2170 选学霸
  • 楼主_7Mr
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/6/1 15:12
  • 上次更新2023/10/23 14:10:29
查看原帖
81pts 求调
602632
_7Mr楼主2023/6/1 15:12

开氧气第一个点不会超时,但是怎么样#8都会错

#include<bits/stdc++.h>
#define int long long
#define INF INT_MAX
using namespace std;
const int maxn=2e5+5;
int n,m,k,cnt,ans;
int dp[maxn],f[maxn],sum1[maxn],sum2[maxn];
int find(int x) {
	if(f[x]==x) return x;
	else return f[x]=find(f[x]);
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>k;
	for(int i=1; i<=n; i++) f[i]=i;
	for(int i=1; i<=k; i++) {
		int x,y;
		cin>>x>>y;
		f[find(x)]=f[find(y)];
	}
	for(int i=1; i<=n; i++) sum1[find(f[i])]++;
	for(int i=1; i<=n; i++) {
		if(sum1[i]!=0) sum2[++cnt]=sum1[i];
	}
	for(int i=1; i<=cnt; i++) {
		for(int j=n; j>=sum2[i]; j--) {
			dp[j]=max(dp[j],dp[j-sum2[i]]+sum2[i]);
		}
	}
	int wh=INF;
	for(int i=1; i<=n; i++){
		if(wh>abs(dp[i]-m)) ans=dp[i],wh=abs(dp[i]-m);
	}
	cout<<ans;
	return 0;
}
2023/6/1 15:12
加载中...