Accumulation Degree

有一個有n個節點，n-1條河道的樹形水系，每個河道有一個最大容水量\(c[x][y]\)表示點x到y的最大容水量，源點可以源源不斷出水，以源點作為根節點的樹的葉子結點可以無限接納水，而一個節點水的流量等于流過其兒子節點的水的流量之和，兒子節點水的流量不能超過其與父親連邊的最大容水量，詢問最大的源點水流量，\(n\leq 2\times 10^5\)。

解

顯然為樹形遞推題，難點在根節點不定，不妨先枚舉根節點，設\(f[x]\)表示以x為根節點的子樹中最大的水流量，不難有

\[f[x]=\sum_{y\in son(x)}min(f[y],c[x][y])\]

邊界：葉子結點f無限大，其余為0

答案：f[r],r為根節點

但是因為枚舉了根節點，時間復雜度為\(O(n^2)\)，所以關鍵在解決根節點，而對于每個根節點求出來的信息，我們并沒有充分利用，借著詢問常用的維護的思想，不妨設\(g[x]\)表示以x為根節點的最大水量，自然也就有

\[g[x]=f[x]+min(g[y]-min(g[y],c[x][y]),c[x][y])\]

于是求出隨便一個根節點的f，然后求出所有g即可，其實這就是二次遞推和換根法。

附錄：

其實注意到葉子節點的特殊性，所以葉子節點的f的轉移方程，需要直接轉移邊權，不進行大小比較，同樣對于g的求法，也要判斷第一次的根節點是否為葉結點，因為它不作為根節點時候，它的流量是無限大，同理當你要求的g為葉結點時，也要特判，因為此時用于轉移g的節點，也就是它的父親節點直接利用的f值為0,是不合法的，所以網上很多的代碼求g時少特判一個葉子結點，所以葉子結點的g值求的是錯的，但是答案顯然是靠中間更優秀，于是是否特判也就無所謂了，所以以下的代碼，也沒有進行特判，難的為了學術的嚴謹，加一點常數,也告訴了我們，一道題目邊界的重要性。

參考代碼：

dfs:

#include <iostream> #include <cstdio> #include <cstring> #define il inline #define ri register #define intmax 0x7fffffff using namespace std; struct point{int next,to,w; }ar[400005];int at; bool check[200005]; int head[200005],f[200005],g[200005],out[200005]; il int min(int,int); void dfs(int),root(int); il void read(int&),link(int,int,int); int main(){int lsy;read(lsy);while(lsy--){int n;read(n),at&=0;memset(f,0,sizeof(f));memset(g,0,sizeof(g));memset(out,0,sizeof(out));memset(head,0,sizeof(head));for(int i(1),j,k,w;i<n;++i)read(j),read(k),read(w),link(j,k,w),link(k,j,w),++out[j],++out[k];dfs(1),g[1]=f[1],root(1);int ans(0);for(int i(1);i<=n;++i)if(ans<g[i])ans=g[i];printf("%d\n",ans);}return 0; } void root(int x){check[x]&=false;for(int i(head[x]);i;i=ar[i].next)if(check[ar[i].to]){if(out[x]==1)g[ar[i].to]=f[ar[i].to]+ar[i].w;else g[ar[i].to]=f[ar[i].to]+min(g[x]-min(ar[i].w,f[ar[i].to]),ar[i].w);//帶了一些未解釋的貪心/*else{if(out[ar[i].to]==1)g[ar[i].to]=f[ar[i].to]+min(g[x]-ar[i].w,ar[i].w);else g[ar[i].to]=f[ar[i].to]+min(g[x]-min(ar[i].w,f[ar[i].to]),ar[i].w); // 實際應該打法}*/root(ar[i].to);} } il int min(int a,int b){return a<b?a:b; } void dfs(int x){check[x]|=true;for(int i(head[x]);i;i=ar[i].next)if(!check[ar[i].to]){dfs(ar[i].to);if(out[ar[i].to]==1)f[x]+=ar[i].w;else f[x]+=min(f[ar[i].to],ar[i].w);} } il void link(int u,int v,int w){ar[++at].to=v,ar[at].w=w;ar[at].next=head[u],head[u]=at; } il void read(int &x){x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); }

bfs

#include <iostream> #include <cstdio> #include <cstring> #define il inline #define ri register #define intmax 0x7fffffff using namespace std; struct point{int next,to,w; }ar[400005];int at; bool check[200005]; int T[200005],head[200005],out[200005],n,f[200005],g[200005],pa[200005],w[200005]; il void read(int&),link(int,int,int),bfs(int); template<class free>il free Min(free,free); int main(){int lsy;read(lsy);while(lsy--){read(n),at&=0;memset(f,0,sizeof(f));memset(g,0,sizeof(g));memset(out,0,sizeof(out));memset(head,0,sizeof(head));memset(check,0,sizeof(check));for(int i(1),j,k,l;i<n;++i)read(j),read(k),read(l),link(j,k,l),link(k,j,l),++out[j],++out[k];bfs(1);int ans(0);for(int i(1);i<=n;++i)if(g[i]>ans)ans=g[i];printf("%d\n",ans);}return 0; } template<class free> il free Min(free a,free b){return a<b?a:b; } il void bfs(int s){int h(0),t(1);T[1]=s;while(h<t){++h,check[T[h]]|=true;for(int i(head[T[h]]);i;i=ar[i].next)if(!check[ar[i].to])T[++t]=ar[i].to,pa[ar[i].to]=T[h],w[ar[i].to]=ar[i].w;}for(int i(n);i;--i){if(out[T[i]]==1)f[pa[T[i]]]+=w[T[i]];else f[pa[T[i]]]+=Min(f[T[i]],w[T[i]]);}g[1]=f[1];for(int i(2);i<=n;++i){if(out[pa[T[i]]]==1)g[T[i]]=f[T[i]]+w[T[i]];else g[T[i]]=f[T[i]]+min(g[pa[T[i]]]-min(w[T[i]],f[T[i]]),w[T[i]]);} } il void link(int u,int v,int w){ar[++at].to=v,ar[at].w=w;ar[at].next=head[u],head[u]=at; } il void read(int &x){x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); }

轉載于:https://www.cnblogs.com/a1b3c7d9/p/10927474.html

總結

以上是生活随笔為你收集整理的Accumulation Degree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。