「LYOI2018 Summer」Hzy's Rabbit Candy
2018-08-07 08:40:04来源:博客园 阅读 ()
「LYOI2018 Summer」Hzy's Rabbit Candy
题目描述
Hzy 和她的 m 只兔兔在一个 n 个点 mmm 条边的有向无环图上玩。
为了让兔兔们开心,Hzy 带了一些糖。Hzy 可以从任何一个点开始,走到任何一个点结束。在这途中,每当 Hzy 经过一个点 iii,她会捡到 aia_ia?i?? 块糖;每当 Hzy 经过一条边 jjj,这条边上的兔兔会吃掉她的 bjb_jb?j?? 块糖。
Hzy 希望能在结束时保留尽量少的糖,请求出 Hzy 在结束时的糖的数量相对于开始时的糖的数量最多减少多少(请注意,Hzy 的糖可能无论如何都无法减少,此时答案是一个非正整数)。
输入格式
第一行两个正整数 nnn、mmm,表示点数和边数。
之后的一行 nnn 个正整数以空格隔开,第 iii 个正整数 aia_ia?i?? 表示经过第 iii 个点 Hzy 会捡到的糖的数量。
之后的 mmm 行,每行三个正整数 uj,vj,bju_j,v_j,b_ju?j??,v?j??,b?j??,表示一条从 uju_ju?j?? 到 vjv_jv?j?? 的边,Hzy 经过这条边时,兔兔会吃掉 bjb_jb?j?? 块糖。
输出格式
一行一个正整数,表示 Hzy 在结束时的糖的数量相对于开始时的糖的数量最多减少多少。
样例输入
3 5
1 2 3
1 2 10
1 2 11
2 3 10
2 3 11
1 3 15
样例输出
16
题目链接 :https://ly.men.ci/problem/398
思路:dp+拓扑排序
实现工具:邻接表
邻接表不会的戳这---->https://www.cnblogs.com/ECJTUACM-873284962/p/6905416.html
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 7 struct edge{ 8 int s,t,next,wi; 9 }edge[500007]; 10 11 long long ans=-100000000; 12 int cnt,head[100007]; //head[u]表示u边的序列号 13 int k[100007] ; // k[i]表示第i个节点所获得的糖果数 14 int in[100007]; //in[i]可以成为边的点 和到它的入度数 15 long long f[100007]; 16 void add(int u,int v,int w){ //邻接表 17 cnt++; 18 edge[cnt].s=u; 19 edge[cnt].t=v; 20 edge[cnt].wi=w; 21 edge[cnt].next=head[u]; //next表示u边的上个序列号 22 head[u]=cnt; //这时在标记当前边的序号,比较优秀的方法 23 24 } 25 int main(){ 26 int n,m; 27 cin>>n>>m; 28 int vi; 29 for(int i=1;i<=n;i++){ 30 cin>>vi; 31 k[i]=vi*(-1); //因为在这道题中求失去的最大值,所以获得就相当于加个负数 32 f[i]=k[i]; 33 ans=max(ans,f[i]); //题面说从任意一点开始到任一点结束,so我们不妨从最大的点开始之后不断更新答案 34 } for(int i=1;i<=m;i++){ 35 36 int u,v,w; 37 cin>>u>>v>>w; 38 add(u,v,w); 39 in[v]++; //因为以v的点都是可以成边的点 40 //将这些点打上标记 ,入度+1 41 } 42 queue<int> q; 43 for(int i=1;i<=n;i++){ 44 if(!in[i])q.push(i); //这样队列中的点都是有边的 45 } 46 47 //开始拓扑排序啦 48 while(!q.empty()){ 49 int u=q.front(); 50 q.pop(); 51 for(int i=head[u];i;i=edge[i].next){ 52 int v=edge[i].t; 53 long long v1=f[u]+edge[i].wi+k[v]; 54 f[v]=max(f[v],v1); //dp,对于当前这个点来说选与不选的价值 55 ans=max(ans,f[v]); //ans更新答案 56 in[v]--;//in数组的作用在这里还有将其入度-1; 57 if(!in[v])q.push(v); //一开始我们是将循环的每个点都pop出去了,但是这个点目前还有入度,所以我们还得将它压进队列 58 } 59 } 60 cout<<ans<<endl; 61 return 0; 62 } 63
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:中山纪念中学培训游记
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash