「LYOI2018 Summer」Hzy's Rabbit Candy
程序员文章站
2022-05-04 13:54:27
「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