題意：一張有向圖，每條邊上都有wi個(gè)蘑菇，第i次經(jīng)過(guò)這條邊能夠采到w-(i-1)*i/2個(gè)蘑菇，直到它為0。問(wèn)最多能在這張圖上采多少個(gè)蘑菇。

分析：在一個(gè)強(qiáng)連通分量?jī)?nèi)，邊可以無(wú)限次地走直到該連通塊內(nèi)蘑菇被采完為止，因此每個(gè)強(qiáng)連通分量?jī)?nèi)的結(jié)果是確定的。

設(shè)一條邊權(quán)值為w，最大走過(guò)次數(shù)為t，解一元二次方程得 t = (int)(1+sqrt(1+8w))；則該邊對(duì)所在連通塊的貢獻(xiàn)為w*t - (t-1)*t*(t+1)/6。

而不在任何一個(gè)強(qiáng)連通分量?jī)?nèi)的邊，最多只能走一次。所以在縮點(diǎn)后的DAG上進(jìn)行dp即可。

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn =1e6+5; struct Edge{int v,next;LL val; }edges[maxn],E[maxn]; int head[maxn],tot,H[maxn],tt; stack<int> S; int pre[maxn],low[maxn],sccno[maxn],dfn,scc_cnt; LL W[maxn]; LL dp[maxn]; void init() {tot = dfn = scc_cnt=tt=0;memset(H,-1,sizeof(H));memset(W,0,sizeof(W));memset(dp,0,sizeof(dp));memset(pre,0,sizeof(pre));memset(sccno,0,sizeof(sccno));memset(head,-1,sizeof(head)); }void AddEdge(int u,int v,LL val) {edges[tot] = (Edge){v,head[u],val};head[u] = tot++; }void Tarjan(int u) {int v;pre[u]=low[u]=++dfn;S.push(u);for(int i=head[u];~i;i=edges[i].next){v= edges[i].v;if(!pre[v]){Tarjan(v);low[u]=min(low[u],low[v]);}else if(!sccno[v]){low[u]=min(low[u],pre[v]);}}if(pre[u]==low[u]){int x;++scc_cnt;for(;;){x = S.top();S.pop();sccno[x]=scc_cnt;if(x==u)break;}} }void nAddEdge(int u,int v,LL w) {E[tt] = (Edge){v,H[u],w};H[u] = tt++; }LL dfs(int u) {if(dp[u]) return dp[u];for(int i=H[u];~i;i=E[i].next){int v = E[i].v;dp[u] = max(dp[u],dfs(v)+E[i].val);}dp[u]+=W[u];return dp[u]; }int main() {#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifint N,M; while(scanf("%d%d",&N,&M)==2){init();int st,u,v; LL w;while(M--){scanf("%d%d%lld",&u,&v,&w);AddEdge(u,v,w);}scanf("%d",&st);for(int i=1;i<=N;++i){if(!pre[i]){Tarjan(i);}}for(int u =1;u<=N;++u){for(int i =head[u];~i;i = edges[i].next){v = edges[i].v;LL w = edges[i].val;if(sccno[u]!=sccno[v]){nAddEdge(sccno[u],sccno[v],w);}else{int t = (int)(1+sqrt(1+8*w))/2;W[sccno[u]] += (LL)t*w - (LL)(t-1)*t*(t+1)/6;}}}for(int i=1;i<=scc_cnt;++i){if(!dp[i]){dfs(i);}}printf("%lld\n",dp[sccno[st]]);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/xiuwenli/p/9494938.html

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 894E Ralph and Mushrooms (强连通缩点+dp)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。