洛谷 P2656 采蘑菇 樹形DP+縮點+坑點
- 2020 年 4 月 4 日
- 筆記
題目鏈接 https://www.luogu.com.cn/problem/P2656
分析
這其實是個一眼題（bushi
發現如果沒有那個恢復係數，縮個點就完了，有恢復係數呢？你發現這個恢復係數其實在DAG中沒有用，因為走不回去不管怎麼恢復都沒啥用，所以對於走不回去的子圖沒有什麼用，於是就想到了縮點，把每個強連通縮成一個點就完了，因為我能恢復的話肯定走的越多越好，所以就把每個強連通都榨乾就完了，統計答案就dp一下，正好剛學的樹形dp，所以大概思路就有了。
我們先通過tarjan跑出強連通分量（有向圖），然後縮點，最後dp，轉移方程也挺簡單的，dp[i]表示以i為跟的子樹，初始化為W[i]
(dp[i]+=max（dp[v]）)我最開始想的版本
但是有一個問題，這麼定義的話縮點前權值在邊上，縮點後權值在點上，我起初的處理辦法是將邊權都壓到邊的終點，因為我只有走過這條邊才能獲得這個權值，乍一看是沒啥問題，但是呢？的確如果從根開始dp不會有問題，但這道題是從某一不定的節點開始dp的，這樣就會出問題。
比如這裡，我t->s這條邊的權值會被壓到s點上，如果我從t開始dp，沒問題，從s開始，明明沒有走那條邊，卻加上了邊權，WA。
解決這個問題很簡單啊，就特判一下，同一個連通分量內的點把權值壓在點上，另外的放在邊上，dp方程改成
(dp[i]+=max（dp[v]+E.val）)
然後這個問題就解決了，這道題一開始Wa的主要原因還是點權邊權的處理，當然也可能是沒想太明白就開始打代碼，導致出現問題，總結一下，以後要先想明白再寫，想出來思路也不一定對
#include<iostream> #include<cstdio> using namespace std; const int N=8e4+10,M=2e5+10; struct Edge{ int fro,nxt,to,val; double hui; }e[M],E[M]; int Head[N],len; void Ins(int a,int b,int c,double d){ e[++len].fro=a;e[len].to=b;e[len].nxt=Head[a]; Head[a]=len;e[len].val=c;e[len].hui=d; } inline int read(){ char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); int x=0; while(ch<='9'&&ch>='0'){ x=x*10+ch-'0'; ch=getchar(); } return x; } int dfn[N],low[N],belong[N],stk[N],top,scc_cnt,num; void tarjan(int u){ dfn[u]=low[u]=++num; stk[++top]=u; for(int i=Head[u];i;i=e[i].nxt){ int v=e[i].to; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(!belong[v])low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ scc_cnt++; while(1){ int x=stk[top--]; belong[x]=scc_cnt; if(x==u)break; } } } int H[N],l,w[N]; void I(int a,int b,int c){ E[++l].to=b;E[l].nxt=H[a];H[a]=l;E[l].val=c; } int dp[N]; void dfs(int u){ if(dp[u])return; dp[u]=w[u]; int now=0; for(int x=H[u];x;x=E[x].nxt){ int v=E[x].to; dfs(v); now=max(now,dp[v]+E[x].val); } dp[u]+=now; } int main(){ int n,m; n=read();m=read(); for(int i=1;i<=m;i++){ int a,b,c;double d; a=read();b=read();c=read();cin>>d; Ins(a,b,c,d); } int s=read(); tarjan(s); for(int i=1;i<=m;i++){ int u=belong[e[i].fro],v=belong[e[i].to]; if(u!=v)I(u,v,e[i].val); if(u==v){ int now=e[i].val;double f=e[i].hui; while(now){ w[v]+=now; now=(int)now*f; } } } dfs(belong[s]); cout<<dp[belong[s]]; } 
