A1387 搭配购买（buy）

#洛谷编号：P1455

经过18次的试错，终于成功了！

思路：

并查集+01背包

因为店主有神经病的要求，我们可以把那些搭配的云通过并查集合并为一件商品统一销售

接着就是01背包问题了，这里不过多赘述，见

A1267 01背包（校外）

A1267 01背包(校内)

代码+解析：

#include<bits/stdc++.h>
using namespace std;
int fa[28571],sumU[28571],sumV[28571],f[28571],n,m,w;//初始化，fa父节点数组，sumU价格数组，sumV价值数组，f背包要用
int Get(int x){return fa[x]==x?x:fa[x]=Get(fa[x]);}
void Merge(int x,int y){fa[Get(x)]=Get(y);}//并查集两大基本函数Get（求根节点），Merge（合并集合）（不会的建议重学）
int main(){
	scanf("%d%d%d",&n,&m,&w);//输入
	for(int i=1;i<=n;i++){fa[i]=i;scanf("%d%d",&sumU[i],&sumV[i]);}//fa数组初始化可以和输入c,d（这里为sumU,sumV）放在一起，省空间
	while(m--){int u,v;scanf("%d%d",&u,&v);Merge(u,v);}//合并为同一商品
	for(int i=1;i<=n;i++)
		if(Get(i)!=i){sumU[Get(i)]+=sumU[i];sumV[Get(i)]+=sumV[i];sumU[i]=sumV[i]=0;}//整集合价格归一
	for(int i=1;i<=n;i++)
		if(Get(i)==i)
			for(int v=w;v>=sumU[i];v--){f[v]=max(f[v],f[v-sumU[i]]+sumV[i]);}//01背包
	printf("%d",f[w]);
	return 0;//自信递交！
}

对着洛谷题解研究了好久，越改越像抄的o(╥﹏╥)o

实际上，我们不仅可以得知正确代码，还可以分析错误代码，以便找bug（当然是自己写的前提下）

90 Wrong Answer代码错误分析

#include<bits/stdc++.h>
using namespace std;
int fa[28571];
int sumU[28571];
int sumV[28571];
int f[28571];
int Get(int x){
	return x==fa[x]?x:fa[x]=Get(fa[x]); 
}
void Merge(int x,int y){
	fa[Get(x)]=Get(y);
}
int main(){
	int n,m,w;//Nitrogen:n;Magnesium:m;Tungstem:w 
	scanf("%d%d%d",&n,&m,&w);
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=n;i++){
		int c,d;
		scanf("%d%d",&c,&d);
		sumU[i]=c;
		sumV[i]=d; 
	}//这里有点冗余，可以合并
	while(m--){
		int u,v;
		scanf("%d%d",&u,&v);
		Merge(u,v);
		sumU[Get(v)]+=sumU[u];
		sumV[Get(v)]+=sumV[u];//最大的问题来了，这里仅是把m个关系数合并了，存在漏加或多加，而且甚至没清零
	}
	for(int i=1;i<=n;i++){
		if(Get(i)==i){
			for(int v=w;v>=sumU[i];v--){
				if(f[v-sumU[i]]+sumV[i]>f[v]){
					f[v]=f[v-sumU[i]]+sumV[i];
				}
			}
		}
	}
	//后面没什么问题
	printf("%d",f[w]);
	return 0;
}//改进方法：多写一个循环，并集后再统一归并价格

另附洛谷题解地址（真的写的挺好的）：点我