所以为什么不用?
by Manchester_Is_Blue @ 2023-07-18 14:49:46
这题很明显,不是用并查集就是用缩点,但是你都没有用,你怎么保证你的做法的正确性?
by WYZ20030051 @ 2023-07-18 14:55:46
这道题可以直接合并
代码如下:
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4+15;;
int n,w,m,a[N],c[N];
int vis[N],id,gc[N],ga[N];
//vector<int> group[N];
int f[N];
signed main(){
scanf("%lld%lld%lld",&n,&m,&w);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&c[i],&a[i]);
for(int i=1;i<=m;i++){
int u,v;scanf("%lld%lld",&u,&v);
if(!vis[u]&&!vis[v]){
vis[u]=vis[v]=++id;
// group[vis[u]].push_back(u);
// group[vis[v]].push_back(v);
ga[vis[u]]+=a[u]+a[v];
gc[vis[u]]+=c[u]+c[v];
}
else if(!vis[u]||!vis[v]){
if(!vis[u]){
vis[u]=vis[v];
//group[vis[v]].push_back(u);
ga[vis[v]]+=a[u];
gc[vis[v]]+=c[u];
}
if(!vis[v]){
vis[v]=vis[u];
//group[vis[u]].push_back(v);
ga[vis[u]]+=a[v];
gc[vis[u]]+=c[v];
}
}
else{
if(vis[u]==vis[v]) continue;
if(vis[u]<vis[v]){
/*for(int j=1;j<=group[vis[v]].size();j++)
group[vis[u]].push_back(group[vis[v]].back()),
group[vis[v]].pop_back();*/
ga[vis[u]]+=ga[vis[v]];ga[vis[v]]=0;
gc[vis[u]]+=gc[vis[v]];gc[vis[v]]=0;
}
else{
/*for(int j=1;j<=group[vis[u]].size();j++)
group[vis[v]].push_back(group[vis[u]].back()),
group[vis[u]].pop_back();*/
ga[vis[v]]+=ga[vis[u]];ga[vis[u]]=0;
gc[vis[v]]+=gc[vis[u]];gc[vis[u]]=0;
}
}
}
for(int i=1;i<=n;i++){
if(!vis[i]){
vis[i]=++id;
ga[vis[i]]=a[i];
gc[vis[i]]=c[i];
}
}
for(int i=1;i<=n;i++){
for(int j=w;j>=gc[i];j--)
f[j]=max(f[j],f[j-gc[i]]+ga[i]);
}
cout<<f[w];
return 0;
}
```
by xiehongxin @ 2023-07-18 15:09:58
```
num[j][k+1]=v;
```
和
```
num[j][k+1]=u;
```
**有问题**
因为不能保证num[j][k+1]是**空的**,如果num[j][k+1]已经**有元素**,那就会被**新的覆盖掉**
可以用**while()**判断**下一个空的位置**,或新建一个cnt数组来保存每个的**现有元素个数**
by JERRYXY @ 2023-07-18 15:34:42