P1455 搭配购买

    • 1.8K通过
    • 4.1K提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 并查集 强连通分量,缩点 背包 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。