「LYOI2018 Summer」Hzy's Rabbit Candy

2018-08-07 08:40:04来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

「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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:1054.求平均数-PAT乙级真题

下一篇:中山纪念中学培训游记