还是并查集,n朵云,m个搭配,和手里的钱w,然后是每朵云的价钱和价值,再是云与云之间的搭配。
思路:
1.还是用combine函数把所有搭配连起来(可能有分散的不知道多少个集合)
2.增加的一个难点就是统计每个集合的总价钱和总价值 (每个集合的根节点都还是初始化的-1)
3.将每个集合的总价值比较,求出总价值最大且总价钱不超过w的
难点的解决办法:
每朵云都有编号,parent[编号]就代表这朵云的父节点所代表的云的编号,根节点的父节点的值是-1,在每一次的结合过程中,把结合进去的云或云集合(两个云集合也只要看根节点就可以了)的价钱和价值都加到根节点上,那么找到parent[编号]=-1的云就可以知道该集合的总价值和总价钱了。
敲代码的过程中又想到一点:可不可以买多个集合,只要总价钱没超过w(这个问题就类似《PERKET》和《kkksc03考前临时抱佛脚》了),但是加上这个点感觉太复杂了,先不考虑了,测试没过再看看。
代码敲出来运行结果不对,不过答题思路没问题,调试了几个细节,改完后样例结果对了,但是没过,还是再考虑考虑那个复杂的情况吧
错误代码:
#include<iostream>
#include<stdio.h>
using namespace std;
int n,m,w;//n朵云,m个搭配,你现有的钱的数目
int c[10010],d[10010];//把1-n朵云的价钱和价值都用数组记录
int maxvalue=0;
#define MAX_TREE_SIZE 10010
int parent[MAX_TREE_SIZE];
int deep[MAX_TREE_SIZE];
void initial(int n);
int find_root(int x);
void combine(int x,int y);
int main()
{
cin>>n>>m>>w;//1<=n<=10000,0<=m<=5000
initial(n);//开始这里没初始化,第一次运行输入的时候出现了问题
for(int i=1;i<=n;i++)
{
cin>>c[i]>>d[i];//第i朵云的价钱和价值
}
int u,v;
for(int i=1;i<=m;i++)
{
cin>>u>>v;//搭配u云和v云,u、v也是编号
combine(u,v);
}
for(int i=1;i<=n;i++)
{
//cout<<"编号="<<i<<" parent[]="<<parent[i]<<endl;
if(parent[i]==-1)//找到根节点
{
//cout<<"d[i]="<<d[i]<<endl;
if(d[i]>maxvalue&&c[i]<=w)
{
maxvalue=d[i];
}
//cout<<"i="<<i<<" maxvalue="<<maxvalue<<endl;
}
}
cout<<maxvalue;//输出可以获得的最大价值
}
void initial(int n)
{
for(int i=1;i<=n;i++)//第二次运行结果错误是因为这里没注意要改,打成了( int i=0;i<n;i++),导致parent[5]=0,没有初始化
{
parent[i]=-1;
deep[i]=0;
}
}
int find_root(int x)
{
int x_root=x;
while(parent[x_root]!=-1)
{
x_root=parent[x_root];
}
return x_root;
}
void combine(int x,int y)
{
int x_root=find_root(x);
int y_root=find_root(y);
if(x_root!=y_root)
{
if(deep[x_root]>deep[y_root])
{
parent[y_root]=x_root;
c[x_root]+=c[y_root];//总价钱
d[x_root]+=d[y_root];//总价值
}
else if(deep[x_root]<deep[y_root])
{
parent[x_root]=y_root;
c[y_root]+=c[x_root];
d[y_root]+=d[x_root];
}
else
{
parent[y_root]=x_root;
c[x_root]+=c[y_root];
d[x_root]+=d[y_root];
deep[x_root]++;
}
}
}
看了下题解的思路,果然是要把并查集和动态规划的01背包问题结合起来
害,继续码