求助
查看原帖
求助
420102
phmaprostrate楼主2021/8/11 19:10

WA 4个 T一个

size中有0会影响结果吗?

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
const int N = 2e4 + 10; 
int fa[N],size[N];
int dp[N];
inline void init(){
 for(int i = 1;i <= N - 20;i++){
	 fa[i] = i;
	 size[i] = 1;
 } 
}
int get(int x){
	if(x == fa[x]) return x;
	else return fa[x] = get(fa[x]);
}
void modify(int x,int y){
	 x = get(x);y = get(y);
	fa[x]  = y;
	 size[y] += size[x];
	 size[x] = 0;
}
int main(){
	cin >>n >> m>> k; 
	init();
	for(int i = 1;i <= k;i++){
		int a,b;
		cin >>a >>b;
		modify(a,b);
	}
      for(int i = 1;i <= n;i++){
      	for(int j = m;j >= size[i];j--){
      		if(j >= size[i]) dp[j] = max(dp[j - size[i]] + size[i],dp[j]);
		  }
	  }
	  cout<< dp[m];
	return 0;
}
2021/8/11 19:10
加载中...