簡單來說，這是一道樹形結(jié)構(gòu)上的最大流問題。

樸素的解法是可以以每個節(jié)點為源點，單獨進行一次dp，時間復(fù)雜度是\(O(n^2)\)
但是在樸素求解的過程中，相當于每次都求解了一次整棵樹的信息，會做了不少的重復(fù)工作。
對于一棵子樹的孩子節(jié)點和根節(jié)點之間存在著最優(yōu)解的某些關(guān)聯(lián)，因此可以采用自頂向下的一次 dfs 遍歷求得結(jié)果。

階段：子樹大小
狀態(tài)：當前子樹大小的情況下，最大的流量是多少
狀態(tài)轉(zhuǎn)移方程：見代碼

代碼如下

#include <cstdio> #include <vector> #include <memory.h> using namespace std; const int maxn=2e5+10;int n,rt,d[maxn],f[maxn],deg[maxn]; struct node{int to,w;node(int x=0,int y=0):to(x),w(y){} }; vector<node> G[maxn];#define cls(a,b) memset(a,b,sizeof(a)) void init(){cls(d,0);cls(f,0);cls(deg,0);for(int i=1;i<=2e5;i++)G[i].clear(); }inline void add_edge(int from,int to,int w){G[from].push_back(node(to,w)),++deg[from];G[to].push_back(node(from,w)),++deg[to]; }void read_and_parse(){scanf("%d",&n);for(int i=1;i<n;i++){int from,to,w;scanf("%d%d%d",&from,&to,&w);add_edge(from,to,w);} }void dfs1(int u,int fa){for(int i=0;i<G[u].size();i++){int v=G[u][i].to,w=G[u][i].w;if(v==fa)continue;dfs1(v,u);if(deg[v]==1)d[u]+=w;else d[u]+=min(w,d[v]);} }void dfs2(int u,int fa){for(int i=0;i<G[u].size();i++){int v=G[u][i].to,w=G[u][i].w;if(v==fa)continue;if(deg[u]==1)f[v]=d[v]+w;else f[v]=d[v]+min(f[u]-min(w,d[v]),w);dfs2(v,u);} }void solve(){rt=1;dfs1(rt,0);f[rt]=d[rt];//自頂向下需要初始化dfs2(rt,0);int ans=0;for(int i=1;i<=n;i++)ans=max(ans,f[i]);printf("%d\n",ans); }int main(){int T;scanf("%d",&T);while(T--){init();read_and_parse();solve();}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/wzj-xhjbk/p/9871141.html

總結(jié)

以上是生活随笔為你收集整理的【POJ3585】Accumulation Degree 二次扫描与换根法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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