题目

传送门= ̄ω ̄=

题目描述

明天就是母亲节了,电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢?听说在某个网站上有卖云朵的,小朋友们决定一同前往去看看这种神奇的商品,这个店里有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;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *