并查集+分组背包
#include<bits/stdc++.h>
using namespace std;
#define xyf main

int n,Wmax,k,root[1010],ans;
vector<int>edges[1010];
int dp[1010];
struct node
{
int p,w;
}robot[1010];
inline int getRoot(int x)
{
return root[x]==x?x:root[x]=getRoot(root[x]);
}
inline bool sameRoot(int x,int y)
{
x=getRoot(x);
y=getRoot(y);
if(x==y)
return 1;
return 0;
}
inline void myunion(int x,int y)
{
if(sameRoot(x,y))
return;
x=getRoot(x);
y=getRoot(y);
root[x]=y;
}
int xyf()
{
ios::sync_with_stdio(false);
cin>>n>>Wmax>>k;
for(int i=1;i<=n;++i)
{
cin>>robot[i].p>>robot[i].w;
root[i]=i;
}
for(int i=1;i<=k;++i)
{
int a,b;
cin>>a>>b;
myunion(a,b);
}
for(int i=1;i<=n;++i)edges[getRoot(i)].push_back(i);
for(int i=1;i<=n;++i)
for(int j=Wmax;j>=0;--j)
for(int o=0;o<edges[i].size();++o)
{
int now=edges[i][o];
if(j>=robot[now].w)
dp[j]=max(dp[j],dp[j-robot[now].w]+robot[now].p);
}
cout<<dp[Wmax]<<endl;
return 0;
}
题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题
题题题题题题题题题题题题题题题题题题题题题题题题题题题题水水水水题题题题题
题题题题题题题题题题题题题题题题题题题题题题题题水水水水水水水水水题题题题
题题题题题题题题题题题题题题题题题题水水水水水水水水水水水水水水水题题题题
题题题题题题题题题题题题题题题题水水水水水水水水水水水水水水水题题题题题题
题题题题题题题题题题题水水水水题水水水水水水水水水水水题题题题题题题题题题
题题题题题题题题水水水水水水水题水水水题题水水水水水题题题题题题题题题题题
题题题水水水水水水水水水水水水题题题题题题水水水水题题题题题题题题题题题题
题水水水水水水水水水水水水水水题题题题题题水水水水题题题题题题题题题题题题
题水水水水水水水水水水水水题题题题题题题水水水水水水水水水水水题题题题题题
题水水水水水水水水水水水水题题题题题题水水水水水水水水水水水水水水题题题题
题题水水水水水水水水水水题题题题题水水水水水水题题题水水水水水水水题题题题
题题题题题题题题水水水水题题题题题水水水水题题题题题题水水水水水题题题题题
题题题题题题题题水水水水题题题题水水水水题题水水题题题水水水水水题题题题题
题题题题题题题题水水水水题题题题水水水水题题水水水水题水水水水水题题题题题
题题题题题题题题水水水水题题题题水水水水题题水水水水题水水水水水题题题题题
题题题题题题题题水水水水题题题题水水水水题题水水水题题水水水水水题题题题题
题题题题题题题题水水水水题题题题水水水水题题水水水题题水水水水水题题题题题
题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题
题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题
题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题
题题题题题题题题水水水水题题题题水水水水题水水水水题题水水水水水题题题题题
题题题题题题题题水水水水题题题题水水水题题水水水水题题水水水水水题题题题题
题题水水题题题水水水水水题题题题水水水题题水水水题题题水水水水水题题题题题
题题水水水水水水水水水水题题题题题水水题题水水题题题题水水水水水题题题题题
题题题水水水水水水水水水题题题题题题题题水水水题题题题水水水水题题题题题题
题题题题题水水水水水水水题题题题题题题题水水水题水水水水题题题题题题题题题
题题题题题题水水水水水水题题题题题题题水水水水题题水水水水题题题题题题题题
题题题题题题题题题水水水题题题题题题水水水水水题题题水水水水水水水题题题题
题题题题题题题题题题题题题题题题水水水水水水题题题题题水水水水水水题题题题
题题题题题题题题题题题题题题题水水水水水水题题题题题题水水水水水水水题题题
题题题题题题题题题题题题题题水水水水水题题题题题题题题题水水水水水水题题题
题题题题题题题题题题题题题水水水水水题题题题题题题题题题题水水水水题题题题
题题题题题题题题题题题题水水水题题题题题题题题题题题题题题题水水水题题题题
题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题题

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n,w,b,fa[1001],cn[1001],c[1001][1000],f[1001][10001],g=0;

struct node1
{
    int p,w;
}a[1001];

int find_fa(int x)
{
    if (fa[x]==x)
        return x;
    else
    {
        fa[x]=find_fa(fa[x]);
        return fa[x];
    }
}

void union_fa(int x,int y)
{
    fa[x]=find_fa(x);
    if (fa[x]!=find_fa(y))
        fa[find_fa(y)]=fa[x];
}

void p_c()
{
    int cx[1001];
    memset(cx,0,sizeof(cx));
    memset(cn,0,sizeof(cn));
    for (int i=1;i<=n;i++)
        if (fa[i]==i||fa[i]==0)
        {
            g++;
            c[g][++cn[g]]=i;
            cx[i]=g;
        }
    for (int i=1;i<=n;i++)
        if (!(fa[i]==i||fa[i]==0))
        {
            int x=cx[find_fa(i)];
            c[x][++cn[x]]=i;
        }
}

int main()
{
    scanf("%d%d%d",&n,&w,&b);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].p,&a[i].w);
        fa[i]=i;
    }
    for (int i=1;i<=b;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        union_fa(x,y);
    }
    p_c();
    memset(f,0,sizeof(f));
    for (int i=1;i<=g;i++)
        for (int j=w;j>=0;j--)
            for (int k=1;k<=cn[i];k++)
            {
                f[i][j]=max(f[i-1][j],f[i][j]);
                if (j>=a[c[i][k]].w)
                    f[i][j]=max(f[i][j],f[i-1][j-a[c[i][k]].w]+a[c[i][k]].p);
            }
    printf("%d\n",f[g][w]);
}

并查集+物品合并

#include <iostream>

using namespace std;

int n,mw,m;
int fa[1000];
int re[1000][1001]={0};
int dp[1001]={0};

int fi(int x)
{
    if(fa[x]==x)
    {
        return x;
    }
    else
    {
        return fa[x]=fi(fa[x]);
    }
}

int main()
{
    cin>>n>>mw>>m;
    int i,j,k,a,b,af,bf;
    for(i=0;i<n;i++)
    {
        cin>>a>>b;
        fa[i]=i;
        for(j=mw;j>=b;j--)
        {
            re[i][j]=re[i][j-b]+a;
        }
    }
    for(i=0;i<m;i++)
    {
        cin>>a>>b;
        a--;
        b--;
        af=fi(a);
        bf=fi(b);
        fa[bf]=af;
        for(j=mw;j>=0;j--)
        {
            re[af][j]=max(re[af][j],re[bf][j]);
        }
    }
    for(i=0;i<n;i++)
    {
        if(i==fi(i))
        {
            for(j=mw;j>=0;j--)
            {
                for(k=0;k<=j;k++)
                {
                    dp[j]=max(dp[j],dp[k]+re[i][j-k]);
                }
            }
        }
    }
    cout<<dp[mw]<<endl;
    return 0;
}

看来要去补一补背包知识了。

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
struct DA {int p,w;} da[1010];
int n,mxw,k;
int fa[1010];
int dp[1010];
vector<int> eg[1010];
int find(int p) {return fa[p]==p?p:fa[p]=find(fa[p]);}
void uin (int pa,int pb) {int fpa=find(pa),fpb=find(pb);if (fpa==fpb) return;fa[fpa]=fpb;}
int main () {
    
    ios::sync_with_stdio(false);
    cin>>n>>mxw>>k;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++) cin>>da[i].p>>da[i].w;
    for(int i=1;i<=k;i++) {int a,b;cin>>a>>b,uin(a,b);}
    for(int i=1;i<=n;i++) eg[find(i)].push_back(i);
    int ans=0;
    for(int i=1;i<=n;i++) 
      for(int j=mxw;j>=0;j--) 
        for(int o=0;o<eg[i].size();o++) {
            int now=eg[i][o];
            if (j>=da[now].w) dp[j]=max(dp[j],dp[j-da[now].w]+da[now].p);
            ans=max(ans,dp[j]);
        }
    cout<<ans<<endl;  
    return 0;
    
}

分组（并查集）背包
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

typedef pair<int, int> PII;
const int N = 1000 + 5;

int n, w, k, pa[N], pos[N], dp[N][N];
PII a[N];
vector<int> zu[N];

int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }

int main() {
scanf("%d%d%d", &n, &w, &k);
for (int i = 1; i <= n; i++)
scanf("%d%d", &a[i].first, &a[i].second);
for (int i = 1; i <= n; i++) pa[i] = i;
for (int i = 1; i <= k; i++) {
int a, b; scanf("%d%d", &a, &b);
pa[findset(a)] = findset(b);
}
int cnt = 0;
for (int i = 1; i <= n; i++)
if (!pos[findset(i)]) {
pos[findset(i)] = ++cnt;
zu[cnt].push_back(i);
} else zu[pos[findset(i)]].push_back(i);
for (int i = 1; i <= cnt; i++)
for (int j = w; j >= 0; j--) {
dp[i][j] = dp[i - 1][j];
for (int q = 0; q < zu[i].size(); q++) {
if (j - a[zu[i][q]].second < 0) continue;
dp[i][j] = max(dp[i][j], dp[i - 1][j - a[zu[i][q]].second] + a[zu[i][q]].first);
}
}
printf("%d\n", dp[cnt][w]);
return 0;
}

经过十几次的提交终于过了，之后的10几次都是错在并查集的合并上
找到a，b的父亲ai,bi后应该是两个父亲节点合并：fa[ai]=bi;(或fa[ai]=b;)f而不是fa[a]=b;或者fa[a]=bi;
前两个都可以，后两个是错误的
#include <cstdio>
#include <algorithm>
using namespace std;
int f[1001]={0},w[1001]={0},p[1001]={0},fa[1001]={0},n,Wmax,k,zu[1001][1001]={0};
int find(int a)
{
if(fa[a]!=a) return fa[a]=find(fa[a]);
else return a;
}
void merge(int a,int b)
{
int x=find(a),y=find(b);
if(x!=y) fa[y]=x;
}
void scan()
{
int a,b,tem;
scanf("%d%d%d",&n,&Wmax,&k);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&p[i],&w[i]);
}
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=k;i++)
{
scanf("%d%d",&a,&b);
merge(a,b);
}
for(int i=1;i<=n;i++)
{
tem=find(i);
zu[tem][ ++zu[tem][0] ]=i;
}
}
void work()
{
for(int i=1;i<=n;i++)
{
if(zu[i][0]!=0)
for(int j=Wmax;j>=0;j--)
for(int q=1;q<=zu[i][0];q++)
{
int aa=zu[i][q];
if(j>=w[aa]) f[j]=max(f[j],f[j-w[aa]]+p[aa]);
}
}
printf("%d",f[Wmax]);
}
int main()
{
// freopen("x.in","r",stdin);
scan();
work();
return 0;
}

少打了一个0，居然改了一上午。。。我也是醉了。
并不会大神们的vector，自己编了个struct，道理是一样的吧。。。另外，背包九讲是好东西，分组背包一定要看
不说了，心累，上代码
#include<iostream>
using namespace std;
int bi[1007] = {0}, f[1007] = {0};//bi：找到祖先，f：背包
int p[1007] = {0}, w[1007] = {0}, bom[1007][2] = {0};//价值，重量，爆炸
int n, wmax, k;
int count = 0, cnt[1007] = {0};
struct g{int pi[1007], wi[1007], flag;} group[1007];
int find(int x)
{
if(bi[x] == x)
return x;
else bi[x] = find(bi[x]);
return bi[x];
}

int main()
{
cin >> n >> wmax >> k;
for(int i = 1; i <= n; i++)
cin >> p[i] >> w[i];
for(int i = 1; i <= n; i++)
bi[i] = i;
for(int i = 1; i <= k; i++)
{
cin >> bom[i][0] >> bom[i][1];
bi[find(bom[i][0])] = find(bom[i][1]);
}
for(int i = 1; i <= n; i++)
{
int x = 0;
for(int j = 1; j <= count; j++)
{
if(find(i) == group[j].flag)
{
cnt[j]++;
group[j].pi[cnt[j]] = p[i];
group[j].wi[cnt[j]] = w[i];
x++;
break;
}
}
if(x == 0)
{
count++;
group[count].pi[1] = p[i], group[count].wi[1] = w[i], group[count].flag = find(i);
cnt[count] = 1;
}
}
for(int i = 1; i <= count; i++)
for(int j = wmax; j >= 0; j--)
for(int k = 1; k <= cnt[i]; k++)
f[j] = j >= group[i].wi[k] ? max(f[j], f[j - group[i].wi[k]] + group[i].pi[k]) : f[j];
cout << f[wmax];
return 0;
}

写getf的时候写错了，容量为负数的时候是不存在，而非直接取容量为零，而且并查集总是会出现各种诡异的错误T_T
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

using namespace std;

int n, wmax, k;
int p[1005], w[1005];
int father[1005];
vector<int> q[1005];
bool vis[1005];
int f[2][10005];

int max0(int a, int b, int c) {
return max(a, max(b, c));
}
int getroot(int x) {
return (father[x] == x ? x : father[x] = getroot(father[x]));
}
void merge(int x, int y) {
if (getroot(x) != getroot(y))
father[getroot(x)] = y;
}
int getf(int x, int y) {
if (y < 0)
return -2000000000;
return f[x][y];
}
int main(int argc, const char *argv[]) {
scanf("%d %d %d", &n, &wmax, &k);
for (int i = 1; i <= n; ++i) {
scanf("%d %d", &p[i], &w[i]);
}
int x, y;
for (int i = 1; i <= n; ++i) father[i] = i;
for (int i = 1; i <= k; ++i) {
scanf("%d %d", &x, &y);
merge(x, y);
}
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (vis[i])
continue;
++cnt;
for (int j = i; j <= n; ++j) {
if (vis[j]) continue;
if (getroot(i) == getroot(j)) {
vis[j] = true;
q[cnt].push_back(j);
}
}
}
int now, prev;
now = 1;
prev = 0;
for (int i = 1; i <= cnt; ++i) {
int qsize = q[i].size();
for (int j = 0; j < qsize; ++j) {
for (int k = 0; k <= wmax; ++k) {
f[now][k] = max0(f[now][k], f[prev][k], getf(prev, k - w[q[i][j]]) + p[q[i][j]]);
}
}
swap(now, prev);
}
printf("%d\n", f[prev][wmax]);
return 0;
}

并查集秒写，然而分组背包......
program p1250;
var
father,p,w,f:array[0..1200] of longint;
a:array[1..1200,0..1200] of longint;
n,wm,k,i,j,v,x,y,num,num1:longint;
function fmax(x,y:longint):longint;
begin
if x>=y then
exit(x)
else exit(y);
end;
function getfather(x:longint):longint;
begin
if father[x]=x then
exit(x)
else begin
father[x]:=getfather(father[x]);
exit(father[x]);
end;
end;
procedure merge(x,y:longint);
var
fa1,fa2:longint;
begin
fa1:=getfather(x);
fa2:=getfather(y);
father[fa1]:=fa2;
end;
function judge(x,y:longint):boolean;
var
fa1,fa2:longint;
begin
fa1:=getfather(x);
fa2:=getfather(y);
if fa1=fa2 then
judge:=true
else judge:=false;
end;
begin
readln(n,wm,k);
for i:=1 to n do
readln(p[i],w[i]);
for i:=1 to n do
father[i]:=i;
for i:=1 to k do
begin
readln(x,y);
merge(x,y);
end;
num:=0;
for i:=1 to n do
if father[i]=i then
begin
inc(num);
num1:=0;
for j:=1 to n do
begin
if judge(i,j) then
begin
inc(num1);
a[num,num1]:=j;
end;
end;
a[num,0]:=num1;
end;
{for i:=1 to num do
for j:=1 to a[i,0] do
for v:=wm downto w[a[i,j]] do
f[v]:=fmax(f[v],f[v-w[a[i,j]]]+p[a[i,j]]);}
for i:=1 to num do
for v:=wm downto 0 do
for j:=1 to a[i,0] do
if w[a[i,j]]<=v then
f[v]:=fmax(f[v],f[v-w[a[i,j]]]+p[a[i,j]]);
writeln(f[wm]);
end.

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define sz 1010
#define for1(v,a,b) for (int v=a;v<=b;v++)
#define for2(v,a,b) for (int v=a;v>=b;v--)
using namespace std;
int n,num,maxn;
int w[sz],f[sz],fa[sz],p[sz];
vector<int>team[sz];
int find(int x){
int t,tt;
t=x;
while (fa[x]!=x)
x=fa[x];
while (fa[t]!=t){
tt=fa[t];
fa[t]=x;
t=tt;
}
return x;
}
int main(){
//freopen("p1.in","r",stdin);
scanf("%d%d%d",&n,&maxn,&num);
for1(i,1,n){
scanf("%d%d",&p[i],&w[i]);
fa[i]=i;
}
for1(i,1,num){
int a,b;
scanf("%d%d",&a,&b);
a=find(a);
b=find(b);
if (a!=b) fa[a]=b;
}
for1(i,1,n){
int x=find(i);
team[x].push_back(i);
}
int cnt=0;
for1(i,1,n)
if (!team[i].empty()){
for2(j,maxn,0)
for (int k=0;k<team[i].size();k++){ //就这句，偷懒惹的祸。。。
int pp=team[i][k];
if (j>=w[pp])
f[j]=max(f[j-w[pp]]+p[pp],f[j]);
}
}

printf("%d\n",f[maxn]);
return 0;
}

思路楼上的各位大神都说了，我就贴代码了

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <cctype>
#define MP(a, b) make_pair(a, b)
using namespace std;
const int MAXN = 1000 + 5;
const int INF = 0x3f3f3f3f;
 
struct EQP
{
    int val, w;
}eqp[MAXN];
 
vector<int> ve[MAXN];
int dp[MAXN][10000], pa[MAXN];
 
int Find(int x)
{
    return pa[x] == x ? x : pa[x] = Find(pa[x]);
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, wMax, k, i, j;
    scanf("%d%d%d", &n, &wMax, &k);
    for (i = 1; i <= n; i++)
        scanf("%d%d", &eqp[i].val, &eqp[i].w);
    for (i = 1; i <= n; i++)
        pa[i] = i;
    for (i = 0; i < k; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int x = Find(a), y = Find(b);
        if (x != y)
            pa[x] = y;
    }
    for (i = 1; i <= n; i++)
    {
        int x = Find(i);
        ve[x].push_back(i);
    }
    int cnt = 0;
    for (i = 1; i <= n; i++)
    {
        if (!ve[i].empty())
        {
            cnt++;
            for (j = 0; j <= wMax; j++)
            {
                dp[cnt][j] = dp[cnt - 1][j];
                for (int k = 0; k < ve[i].size(); k++)
                    if (j >= eqp[ve[i][k]].w)
                        dp[cnt][j] = max(dp[cnt][j], dp[cnt - 1][j - eqp[ve[i][k]].w] + eqp[ve[i][k]].val);
            }
        }
    }
    printf("%d\n", dp[cnt][wMax]);
    return 0;
}

很明显的并查集+背包
但是注意找同一个集合的元素时不能直接调用father数组（路径压缩后的也不行吧）
要用getfather找到祖先
贴个AC代码
program vj;
var n,w,tt,k,a,b,i,j,z,t1,t2:longint;
f,p,ww,father,use,son:array[0..2000] of longint;
num:array[0..2000,0..2000] of longint;

function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;

function getfather(k:longint):longint;
var tip:longint;
begin
if father[k]=k then exit(k);
tip:=father[k];
father[k]:=getfather(tip);
exit(father[k]);
end;

begin
readln(n,w,k);
for i:=1 to n do
readln(p[i],ww[i]);
for i:=1 to n do
father[i]:=i;
for i:=1 to k do
begin
readln(a,b);
t1:=getfather(a);
t2:=getfather(b);
father[t1]:=t2;
end;
for i:=1 to n do
begin
use[i]:=getfather(i);
inc(son[use[i]]);
num[use[i],son[use[i]]]:=i;
end;
for i:=1 to n do
if son[i]<>0 then
for j:=w downto 1 do
for z:=1 to son[i] do
if j-ww[num[i,z]]>=0 then
f[j]:=max(f[j],f[j-ww[num[i,z]]]+p[num[i,z]]);
writeln(f[w]);
end.

试一试能不能发出去

并查集+dp
n^2搞定
分析，首先并查集并集，然后就是dp
dp思路如下
f[i][j]表示前i个集合中，（也就是说把一个集合看做一个元素去更新f的值，当然可以这个集合中的一个也不上。一开始忘了这一点）花费为j可得的最大价值
所以容易得到状态转移方程（这个自己推导）
代码如下。
#include<cstdlib>
#include<cstdio>
#include<cstring>
#define N 1000
#define P 1000
int fa[N],v[N],c[N];
int n,p,cmax;
int f[2][P];
int get_fa(int a)
{
if (a == fa[a]) return a; else return fa[a] = get_fa(fa[a]);
}

int max(int x,int y)
{
if (x > y) return x; else return y;
}

void swap_intp(int **a,int **b)
{
int *t;
t = *a; *a = *b; *b = t;
}

void dp()
{
int cost,i,j,fa_v;
int *f1,*f2;
memset(f,0,sizeof(int)*2*P);
//for (i = 0;i < cmax;i++) f[0][i] = f[1][i] = 0;
f1 = f[0]; f2 = f[1];
for (j = 0;j < n;j++) {
if (fa[j] >= 0) fa_v = fa[j]; else continue;
//memset(f2,0,sizeof(int)*P);注意我注释掉了这一行，第一次就是由于这一行出错
for (i = 0;i < cmax;i++) *(f2+i) = *(f1+i); //这一行是第二次加上去得。因为可以这个集合中的一个也不选。若是没有。也就是说这个集合中的元素选了只有比之前的更差的份，如果不先把之前的状态copy回来。那么就会出现错误。例如前4个集合中花费1就可以最多得到100000,而如果不copy，可能就会算出这个集合的元素中所能获得的最优值是100,然后就错误的得出前5个集合花费1就可以最多得到100（这显然错误）
for (i = 0;i < n;i++) {
if (fa[i] != fa_v) continue; else fa[i] = -1;
for (cost = 1;cost <= cmax;cost++)
if (cost > c[i])
(f2+cost-1) = max((f1+cost-c[i]-1)+v[i],*(f2+cost-1));
else if (cost == c[i]) (f2+cost-1) = max(v[i],(f2+cost-1));
}
swap_intp(&f1,&f2);
}
for (i = 0,j = 0;i < cmax;i++) j = max(j,*(f1+i));
printf("%d\n",j);
printf("%d\n",*(f1+cmax-1));
}
int main()
{
void init();
init(); dp();
return 0;
}

void init()
{
int x,y;
scanf("%d%d%d",&n,&cmax,&p);
for (int i = 0;i < n;i++) {
fa[i] = i; scanf("%d%d",v+i,c+i);
}
for (int i = 0;i < p;i++) {
scanf("%d%d",&x,&y); fa[get_fa(x-1)] = get_fa(y-1);
}
for (int i = 0;i < n;i++) get_fa(i);
}

测试数据 #0: Accepted, time = 3 ms, mem = 4380 KiB, score = 10

测试数据 #1: Accepted, time = 2 ms, mem = 4384 KiB, score = 10

测试数据 #2: Accepted, time = 1 ms, mem = 4376 KiB, score = 10

测试数据 #3: Accepted, time = 1 ms, mem = 4376 KiB, score = 10

测试数据 #4: Accepted, time = 3 ms, mem = 4376 KiB, score = 10

测试数据 #5: Accepted, time = 3 ms, mem = 4380 KiB, score = 10

测试数据 #6: Accepted, time = 3 ms, mem = 4376 KiB, score = 10

测试数据 #7: Accepted, time = 5 ms, mem = 4380 KiB, score = 10

测试数据 #8: Accepted, time = 7 ms, mem = 4380 KiB, score = 10

测试数据 #9: Accepted, time = 1 ms, mem = 4376 KiB, score = 10

Accepted, time = 37 ms, mem = 4384 KiB, score = 100

一个并查集加背包。。。
#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXN 1001
#define MAXW 1001

int f[MAXW][2];
int father[MAXN];

int n,maxw,k;
int w[MAXN],p[MAXN];
int Kind[MAXN][MAXN];

int Find(int x){
int i=x;
while (father[i]){
i=father[i];
}
int j=x;
while (father[j]){
int k=father[j];
father[j]=i;
j=k;
}
return i;
}

void Insert(int x,int y){
father[Find(x)]=Find(y);
}

int main(){
scanf("%d %d %d",&n,&maxw,&k);
for (int i=0;i++<n;){
scanf("%d %d",&p[i],&w[i]);
}
for (int i=0;i++<n;){
father[i]=0;
}
while (k--){
int x,y;
scanf("%d %d",&x,&y);
if (Find(x)!=Find(y)){
Insert(x,y);
}
}
for (int i=0;i++<n;){
Kind[i][0]=0;
}
for (int i=0;i++<n;){
Kind[Find(i)][++Kind[Find(i)][0]]=i;
}
for (int i=0;i<=maxw;i++){
f[i][0]=f[i][1]=0;
}
int z=0;
for (int i=0;i++<n;){
if (Kind[i][0]){
for (int j=0;j<=maxw;j++){
f[j][(k+1)%2]=f[j][k];
}
}
for (int j=0;j++<Kind[i][0];){
int x=Kind[i][j];
for (int h=maxw;h>=w[x];h--){
f[h][(k+1)%2]=max(f[h][(k+1)%2],f[h-w[x]][k]+p[x]);
}
}
if (Kind[i][0]){
k+=1;
k%=2;
}
}
printf("%d\n",f[maxw][k]);
return 0;
}

#include

#include

#include

#include

using namespace std;

int tmp,ans,n,wmax,k;

int w[1001],p[1001],father[1001],f[1001];

bool flag[1001];

int save[1001][1001];

int getfa(int i)

{

if (i==father[i])

return i;

father[i]=getfa(father[i]);

return father[i];

}

int getmax(int i,int j)

{

if (i>j) return i; else return j;

}

int main()

{

ans=0;

memset(flag,0,sizeof(flag));

cin>>n>>wmax>>k;

memset(f,0xff,sizeof(f));

f[0]=0;

for (int i=1;i>p[i]>>w[i];

father[i]=i;

}

int a,b,lx,ly;

for (int i=1;i>a>>b;

lx=getfa(a);

ly=getfa(b);

if (lx != ly)

father[lx]=ly;

}

for (int i=1;i

并查集要这样写，否则会栈溢出（交3次栈溢出）

function parent(nd:longint):longint;

var f,x:longint;

begin

x:=nd;

while true do

begin

if p[x]=x then

begin

p[nd]:=x;

exit(x);

end;

x:=p[x];

end;

end;

var t,n,z,m:integer;

f:array[0..1000] of longint;

a:array[1..1000,1..1000] of integer;

p,w,l,b,h:array[1..1000] of integer;

v:array[1..1000] of boolean;

procedure ready;

var i,j,x,y,x1,y1,q:integer;

begin

readln(n,z,m);

for i:=1 to n do begin readln(p[i],w[i]); h[i]:=i; end;

for i:=1 to m do

begin

readln(x,y);

x1:=h[x]; y1:=h[y];

if x1=0 then

if f[j-w]+p>f[j] then f[j]:=f[j-w]+p;

end;

end;

writeln(f[z]);

end;

begin

ready;

work;

end.

1 次AC

背包问题 想清楚就好

循环顺序的改变就可以处理不同的问题，牛！！

0 to maxw 无限背包

max downto 0 有限背包

///

maxw downto 0

1 to t

分组

1 to t

maxw downto 0

不分组