#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, MAXN = 20005;
int n, m, k, u, v, t[MAXN], w[MAXN], dp[MAXN], father[MAXN];
inline int find(int x) {//并查集
return (x == father[x] ? x : father[x] = find(father[x]));
}
inline void Union(int u, int v) {//合并
int p = find(u), q = find(v);
if (p != q) father[p] = q;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
father[i] = i;
for (int i = 1; i <= k; i++) {
scanf("%d%d", &u, &v);
Union(u, v);//将输入的两个人合并起来
}
for (int i = 1; i <= n; i++)
t[find(i)]++;
int cnt = 0;
for (int i = 1; i <= n; i++)
if (t[i]) w[++cnt] = t[i];//计算价值
for (int i = 1; i <= cnt; i++)
for (int j = m << 1; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + w[i]);//01背包
int Min = INF, ans = 0;
for (int i = 0; i <= m; i++) {
if (dp[m - i] == m - i) {
printf("%d\n", m - i);
return 0;
}
if (dp[m + i] == m + i) {
printf("%d\n", m + i);
return 0;
}
}
return 0;
}
先用并查集将实力相当的并成一个集合,集合的人数就是价值也是体积,m是最大价值尽可能接近所以选出来可以大于m
开两倍,这个要吸氧才能过,还有一个大佬的代码看不太懂
using namespace std;
int n,m,k;
int f[20001];
int t[20001];
int cnt,a[20001];
bool u[20001];
int ans;
int find(int x)
{
if(f[x]==x) return f[x];
f[x]=find(f[x]);
return f[x];
}
void merge(int x,int y)
{
f[find(x)]=f[find(y)];
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(find(x)!=find(y)) merge(x,y);
}
for(int i=1;i<=n;i++) f[i]=find(f[i]);
for(int i=1;i<=n;i++) t[f[i]]++;
for(int i=1;i<=n;i++)
{
if(t[i])
{
a[++cnt]=t[i];
}
}
u[0]=1;
for(int i=1;i<=cnt;i++)
{
for(int j=n-a[i];j>=0;j--)
{
if(u[j]) u[j+a[i]]=1;
}
}
for(int i=1;i<=n;i++)
{
if(u[i]&&abs(ans-m)>abs(i-m)) ans=i;
}
printf("%d",ans);
return 0;
}