Joe觉得云朵很美，决定去山上的商店买一些云朵。商店里有n多云，云朵被编号为1,2，.....n，并且每朵云都有一个价值。
但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。
但是Joe的钱有限，所以他希望买的价值越多越好。

题目概述

有n个点，m条线将它们中的一部分连接，每个点有它的价值和权值。
获得这个点要付出它的权值并获得与它连接的点，求在付出不超过w时，可以获得的最大价值。

输入

第1行：n、m、w，表示n多云，m个搭配，Joe有w的钱

第2至n+1行，每行ci，di表示i朵云的价钱和价值。

第n+2至n+1+m行，每行ui，vi表示买ui就必须买vi，同理，如果买vi就必须买ui。

输出

一行：表示可以获得的最大价值

思路

如下图，有n个点，m条边，并且是双向的，很容易联想到图，
将问题转化为求每个连通块的价值和付出的权值，
再套上01背包模板求最大价值。

代码实现

可以用并查集来储存，然后缩点，但这里我用递推来寻找连通块：

void find(int u)
{
	for(auto it=v[u].begin();it!=v[u].end();it++)//v[i]用于储存以i为定点的连通块所包含的点
	{
		if(vis[*it]==true)//如果这个点之前已经寻找过，那就跳过，避免重复计算
		{
			continue;
		}
		vis[*it]=true;
		nc+=a[*it].c;//nc是这个连通块需付出的权值总和
		nd+=a[*it].d;//nd是连通块可以获得的价值总和
		find(*it);//递归查找
	}
}

Ac Code

#include <bits/stdc++.h>
using namespace std;
//分割线qwq
int n,m,w;
int nc=0,nd=0;
int cnt;
bool vis[10005];
vector<int> v[10005];
int dp[100005];
//分割线qwq
struct yun
{
	int c;
	int d;
}a[10005];
struct cd
{
	int c;
	int d;
}cdd[10005];
//分割线qwq
void find(int u)
{
	for(auto it=v[u].begin();it!=v[u].end();it++)
	{
		if(vis[*it]==true)
		{
			continue;
		}
		vis[*it]=true;
		nc+=a[*it].c;
		nd+=a[*it].d;
		find(*it);
	}
}
//分割线qwq
int main()
{
	cin>>n>>m>>w;
	for(int i=1;i<=n;i++)
	{
		int c,d;
		cin>>c>>d;
		a[i].c=c;
		a[i].d=d;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]==false)
		{
			nc=nd=0;
			vis[i]=true;
			nc+=a[i].c;
			nd+=a[i].d;
			find(i);
			if(nc<=w)
			{
				cnt++;
				cdd[cnt].c=nc; 
				cdd[cnt].d=nd;
			}
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		for(int j=w;j>=cdd[i].c;j--)
		{
			dp[j]=max(dp[j],dp[j-cdd[i].c]+cdd[i].d);
		}
	}
	cout<<dp[w];//01背包，作者不会不会吧qwq
	return 0;
}