洛谷 P1455 搭配购买

洛谷 P1455 搭配购买

洛谷 P1455 搭配购买

还是并查集,n朵云,m个搭配,和手里的钱w,然后是每朵云的价钱和价值,再是云与云之间的搭配。

思路:

1.还是用combine函数把所有搭配连起来(可能有分散的不知道多少个集合)

2.增加的一个难点就是统计每个集合的总价钱和总价值 (每个集合的根节点都还是初始化的-1)

3.将每个集合的总价值比较,求出总价值最大且总价钱不超过w的

难点的解决办法:

每朵云都有编号,parent[编号]就代表这朵云的父节点所代表的云的编号,根节点的父节点的值是-1,在每一次的结合过程中,把结合进去的云或云集合(两个云集合也只要看根节点就可以了)的价钱和价值都加到根节点上,那么找到parent[编号]=-1的云就可以知道该集合的总价值和总价钱了。

敲代码的过程中又想到一点:可不可以买多个集合,只要总价钱没超过w(这个问题就类似《PERKET》和《kkksc03考前临时抱佛脚》了),但是加上这个点感觉太复杂了,先不考虑了,测试没过再看看。

代码敲出来运行结果不对,不过答题思路没问题,调试了几个细节,改完后样例结果对了,但是没过,还是再考虑考虑那个复杂的情况吧

洛谷 P1455 搭配购买 

错误代码:

#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背包问题结合起来

害,继续码

上一篇:C++基础算法教程——高精度算法


下一篇:[JLOI2011]飞行路线题解