题目

传送门=￣ω￣=

题目描述

明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有 n 朵云，云朵已经被老板编号为 1，2，3，……,n, 并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。

输入输出格式

输入格式：

第 1 行 n,m,w, 表示 n 朵云，m 个搭配和你现有的钱的数目

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

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

输出格式：

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

输入输出样例

输入样例 #1：

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

输出样例 #1：

1

说明

30% 的数据满足：n<=100

50% 的数据满足：n<=1000;m<=100;w<=1000;

100% 的数据满足：n<=10000;0<=m<=5000;w<=10000.

题解

实在搞不清这是叫啥连通分量了（双连通分量？）……反正求法其实是很容易的。
首先缩点，把任意两两能互达的点集缩成一个点，再进行 01 背包 dp。这题数据范围要求我们用一维 01 背包。

缩点无需 tarjan、kosaraju，因为是无向图，随便选一个未被染色的点，对它染色并扩展即可。所能扩展到的点都在一个连通块中。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,w,c[10005],d[10005],cnt,cost[10005],val[10005],f[10005];
vector<int> g[10005];
bool book[10005];
void dfs(int u)
{
    book[u]=1,cost[cnt]+=c[u],val[cnt]+=d[u];
    for(vector<int>::iterator i=g[u].begin();i!=g[u].end();i++)
        if(!book[*i])dfs(*i);
}
int main()
{
    scanf("%d%d%d",&n,&m,&w);
    for(int i=1;i<=n;i++)scanf("%d%d",&c[i],&d[i]);
    for(int i=1,a,b;i<=m;i++)
        scanf("%d%d",&a,&b),g[a].push_back(b),g[b].push_back(a);
    for(int i=1;i<=n;i++)if(!book[i])cnt++,dfs(i);
    for(int i=1;i<=cnt;i++)
        for(int j=w;j>=cost[i];j--)
            f[j]=max(f[j],f[j-cost[i]]+val[i]);
    printf("%d\n",f[w]);
    return 0;
}