搭配購買 題目描述

明天就是母親節(jié)了，電腦組的小朋友們在忙碌的課業(yè)之余挖空心思想著該送什么禮物來表達(dá)自己的心意呢？聽說在某個(gè)網(wǎng)站上有賣云朵的，小朋友們決定一同前往去看看這種神奇的商品，這個(gè)店里有 n n n 朵云，云朵已經(jīng)被老板編號為 1 , 2 , 3 , . . . , n 1,2,3,...,n 1,2,3,...,n，并且每朵云都有一個(gè)價(jià)值，但是商店的老板是個(gè)很奇怪的人，他會(huì)告訴你一些云朵要搭配起來買才賣，也就是說買一朵云則與這朵云有搭配的云都要買，電腦組的你覺得這禮物實(shí)在是太新奇了，但是你的錢是有限的，所以你肯定是想用現(xiàn)有的錢買到盡量多價(jià)值的云。

創(chuàng)新互聯(lián)公司主要從事網(wǎng)站設(shè)計(jì)制作、網(wǎng)站制作、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)啟東,十載網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18980820575輸入格式

第一行輸入三個(gè)整數(shù)， n , m , w n,m,w n,m,w，表示有 n n n 朵云， m m m 個(gè)搭配和你現(xiàn)有的錢的數(shù)目。

第二行至 n + 1 n+1 n+1 行，每行有兩個(gè)整數(shù)， c i , d i c_i,d_i ci?,di?，表示第 i i i 朵云的價(jià)錢和價(jià)值。

第 n + 2 n+2 n+2 至 n + 1 + m n+1+m n+1+m 行 ，每行有兩個(gè)整數(shù) u i , v i u_i,v_i ui?,vi?。表示買第 u i u_i ui? 朵云就必須買第 v i v_i vi? 朵云,同理，如果買第 v i v_i vi? 朵就必須買第 u i u_i ui? 朵。

輸出格式

一行，表示可以獲得的大價(jià)值。

樣例 #1 樣例輸入 #1

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

樣例輸出 #1

1

提示

• 對于 30 % 30\% 30% 的數(shù)據(jù)，滿足 1 ≤ n ≤ 100 1 \le n \le 100 1≤n≤100；
• 對于 50 % 50\% 50% 的數(shù)據(jù)，滿足 1 ≤ n , w ≤ 1 0 3 1 \le n, w \le 10^3 1≤n,w≤103， 1 ≤ m ≤ 100 1 \le m \le 100 1≤m≤100；
• 對于 100 % 100\% 100% 的數(shù)據(jù)，滿足 1 ≤ n , w ≤ 1 0 4 1 \le n, w \le 10^4 1≤n,w≤104， 0 ≤ m ≤ 5 × 1 0 3 0 \le m \le 5 \times 10^3 0≤m≤5×103。

算法

這題的算法很簡單啊~~ 就是一個(gè)普通的01背包+并查集。
01背包和并查集想必大家一定都了如指掌，那么我就不講了，下面直接上代碼：

• 并查集文章（小天狼星自己寫的）
• 01背包文章（同上）
• 并查集資源（無需積分/C幣）

好了終于可以安心的給出代碼了👇

#include//相信不會(huì)有人不知道萬能頭吧~
using namespace std;
int v,n,m,a,b,d[20000],c[20000],w[20000],f[20000];
int fr(int x)		//查找根結(jié)點(diǎn)的函數(shù)
{if (x!=f[x])
		x=fr(f[x]);
	return x;
}
int main()
{cin >>n >>m >>v;
	for (int i=1;i<=n;i++)
		f[i]=i;				//初始化并查集
	for (int i=1;i<=n;i++)
		cin >>w[i] >>c[i];		//輸入價(jià)錢和價(jià)格
	for (int i=1;i<=m;i++)
	{cin >>a >>b;	//輸入要合并的兩個(gè)云朵
		f[fr(a)]=fr(b);			//合并a，b
	}
	for (int i=1;i<=n;i++)		//關(guān)鍵循環(huán)
	{int zx=fr(i);
		if (zx!=i)	//如果自己不是首領(lǐng)/祖先，說明自己的祖先是其他人
		{	w[zx]+=w[i];
			c[zx]+=c[i];	//將自己的數(shù)據(jù)加入到=祖先那里
			w[i]=1e+6;		//將自己的價(jià)格設(shè)為大值，讓小朋友買不起
		}
	}
	for (int i=1;i<=n;i++) 
		for (int j=v;j>=w[i];j--)
		{	d[j]=max(d[j],d[j-w[i]]+c[i]);		//01背包模板
		}
	cout<

好了，結(jié)束?。?br />這題你學(xué)會(huì)了嗎？

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：搭配購買——C++詳解-創(chuàng)新互聯(lián)
標(biāo)題路徑：http://www.rwnh.cn/article24/pohje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊、網(wǎng)站導(dǎo)航、做網(wǎng)站、虛擬主機(jī)、網(wǎng)站策劃、微信公眾號

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)