洛谷 P1455 搭配购买
2024-09-08 12:47:11
题目描述
明天就是母亲节了,电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢?听说在某个网站上有卖云朵的,小朋友们决定一同前往去看看这种神奇的商品,这个店里有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.
Tarjan缩点+背包dp
(偷笑)一遍过~
#include <ctype.h>
#include <cstdio>
#define N 5005 void read(int &x)
{
x=;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}
}
struct node
{
int next,to;
}edge[N<<];
struct nodE
{
int c,d;
}cloud[N<<];
bool vis[N<<];
int f[N<<],value[N<<],price[N<<],tim,low[N<<],dfn[N<<],top,head[N<<],stack[N<<],sumcol,col[N<<],cnt,n,m,w;
void add(int u,int v)
{
edge[++cnt].next=head[u];
edge[cnt].to=v;
head[u]=cnt;
}
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a>b?b:a;
}
void dfs(int x)
{
stack[++top]=x;
vis[x]=;
low[x]=dfn[x]=++tim;
for(int i=head[x];i;i=edge[i].next)
{
if(!vis[edge[i].to])
{
dfs(edge[i].to);
low[x]=min(low[x],dfn[edge[i].to]);
}
else low[x]=min(low[x],low[edge[i].to]);
}
if(low[x]==dfn[x])
{
sumcol++;
col[x]=sumcol;
while(stack[top]!=x)
col[stack[top--]]=sumcol;
}
}
int main()
{
read(n);read(m);read(w);
for(int i=;i<=n;i++)
read(cloud[i].c),read(cloud[i].d);
for(int u,v;m--;)
{
read(u);
read(v);
add(u,v);
add(v,u);
}
for(int i=;i<=n;i++) if(!vis[i]) dfs(i);
for(int i=;i<=n;i++)
price[col[i]]+=cloud[i].c,value[col[i]]+=cloud[i].d;
for(int i=;i<=sumcol;i++)
{
for(int j=w;j>=price[i];j--)
f[j]=max(f[j],f[j-price[i]]+value[i]);
}
printf("%d",f[w]);
return ;
}
最新文章
- unity 角色旋转
- 关于一些网络代理实现智能流量分流的研究(PAC脚本介绍及利用)
- Java从零开始学四十五(Socket编程基础)
- 2015ACM/ICPC亚洲区长春站 L hdu 5538 House Building
- nova分析(10)—— nova-rootwrap
- 10分钟学会基于ASP.NET的 JQuery实例 (转)
- JAVA中toString方法
- 移植FreeModbus+ModbusMaster+STM32至RT-Thread(初步)
- 6个可以隐藏运行bat,浏览器等程序的方法
- leetcode修炼之路——83. Remove Duplicates from Sorted List
- Eclipse怎么忽略掉报错的js文件
- C / C++算法学习笔记(7)-双向冒泡
- UVA 538 - Balancing Bank Accounts(贪心)
- C# File类的操作
- cocoapods安装好后repo换源
- .Net程序员学用Oracle系列(29):PLSQL 之批量应用和系统包
- 计时器60s
- Windows环境下多线程编程原理与应用读书笔记(2)————面向对象技术
- Xshell5一打开就提示要使用该程序,请更新至最新版本
- easyUI的汇总列,在前端生成
热门文章
- https证书/即SSL数字证书申请途径和流程
- Oracle常用数据库表操作
- bzoj 4398 福慧双修 —— 二进制分组+多起点最短路
- 微信小程序wxml和wxss样式
- 【转】java对象——new对象的理解
- codeforces 126B
- 使用JavaScript实现弹出层效果的简单实例
- UVaLive 6950 &;&; Gym 100299K Digraphs (DFS找环或者是找最长链)
- 骨骼蒙皮动画(Skinned Mesh)的原理解析(二)
- c++语言中类中的静态数据成员为什么必须在类体外初始化?