欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

「LYOI2018 Summer」Hzy's Rabbit Candy

程序员文章站 2022-10-04 23:24:47
「LYOI2018 Summer」Hzy's Rabbit Candy 题目描述 Hzy 和她的 m 只兔兔在一个 n 个点 mmm 条边的有向无环图上玩。 为了让兔兔们开心,Hzy 带了一些糖。Hzy 可以从任何一个点开始,走到任何一个点结束。在这途中,每当 Hzy 经过一个点 iii,她会捡到  ......

「LYOI2018 Summer」Hzy's Rabbit Candy

 

 

题目描述

Hzy 和她的 m 只兔兔在一个 n 个点 mmm 条边的有向无环图上玩。

为了让兔兔们开心,Hzy 带了一些糖。Hzy 可以从任何一个点开始,走到任何一个点结束。在这途中,每当 Hzy 经过一个点 iii,她会捡到 aia_iai​​ 块糖;每当 Hzy 经过一条边 jjj,这条边上的兔兔会吃掉她的 bjb_jbj​​ 块糖。

Hzy 希望能在结束时保留尽量少的糖,请求出 Hzy 在结束时的糖的数量相对于开始时的糖的数量最多减少多少(请注意,Hzy 的糖可能无论如何都无法减少,此时答案是一个非正整数)。

输入格式

第一行两个正整数 nnn、mmm,表示点数和边数。
之后的一行 nnn 个正整数以空格隔开,第 iii 个正整数 aia_iai​​ 表示经过第 iii 个点 Hzy 会捡到的糖的数量。
之后的 mmm 行,每行三个正整数 uj,vj,bju_j,v_j,b_juj​​,vj​​,bj​​,表示一条从 uju_juj​​ 到 vjv_jvj​​ 的边,Hzy 经过这条边时,兔兔会吃掉 bjb_jbj​​ 块糖。

输出格式

一行一个正整数,表示 Hzy 在结束时的糖的数量相对于开始时的糖的数量最多减少多少。

 

样例输入

3 5
1 2 3
1 2 10
1 2 11
2 3 10
2 3 11
1 3 15

样例输出

16

 

题目链接 :


思路: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