P3128 [USACO15DEC]最大流Max Flow
P3128 [USACO15DEC]最大流Max Flow
對(duì)，這是一道最大流的題目qwq
樹(shù)上跑最大流，沒(méi)錯(cuò)
也就是跑最小割
你看名字里都有最大流，為什么不能跑最大流qwq..............................
編不下去了
跑樹(shù)上差分。
就像數(shù)組上可以進(jìn)行差分一樣，樹(shù)上也可以進(jìn)行差分。適用于樹(shù)上兩點(diǎn)之間的路徑操作，和極少數(shù)的查詢
適用于維護(hù)路徑長(zhǎng)可以進(jìn)行結(jié)合律的操作
比如說(shuō)我們要在樹(shù)上進(jìn)行兩點(diǎn)之間的路徑上的節(jié)點(diǎn)值加一個(gè)數(shù)，最后輸出所有節(jié)點(diǎn)值之和。
我們可以進(jìn)行樹(shù)鏈剖分，可是使用樹(shù)鏈剖分有些大材小用了，而且常數(shù)巨大
我們就可以使用差分
比如說(shuō)這么一棵樹(shù)
我們要使得8到11的路徑上的點(diǎn)加3
我們就可以設(shè)一個(gè)數(shù)組，\(t[i]\)表示這棵樹(shù)的差分?jǐn)?shù)組,\(st[i][j]\)表示樹(shù)上的倍增數(shù)組
然后我們令\(t[8]+=3,t[11]+=3,t[lca_{(8,11)}]-=3,t[st[lca_{(8,11)}][0]]-=3\)
然后我們將差分?jǐn)?shù)組使用以下程序進(jìn)行整理整理，然后進(jìn)行查詢。
void DFS(int now,int fa) {int pas=0;for(int i=head[now];i;i=line[i].nxt)if(line[i].p!=fa){DFS(line[i].p,now);t[now]+=t[line[i].p];} }將所有點(diǎn)上的值遞歸加起來(lái)，就成了下圖的情況。成功實(shí)現(xiàn)了O(1)修改，O(N)查詢
而對(duì)于維護(hù)邊權(quán)呢？我們可以將邊權(quán)下放至所連點(diǎn)中深度最深的點(diǎn)上去
然后將差分時(shí)的\(t[st[lca_{(a,b)}][0]]-=add,t[lca_{(a,b)}]-=add\)變?yōu)?span id="ze8trgl8bvbq" class="math inline">\(t[lca_{(a,b)}]-add*2\)就可以了，樹(shù)鏈剖分也可以將邊權(quán)下放至點(diǎn)
此題\(code\)
#include<cstdio> #include<algorithm> #include<iostream> using std::swap; using std::max; const int maxn=50100; struct node {int p;int nxt; }; node line[maxn<<1]; int head[maxn],tail; void add(int a,int b) {line[++tail].p=b;line[tail].nxt=head[a];head[a]=tail; } int st[maxn][20]; int log[maxn]; int dep[maxn]; int ans,t[maxn]; void dfs(int now,int fa) {st[now][0]=fa;dep[now]=dep[fa]+1;for(int i=1;i<=log[dep[now]];i++)st[now][i]=st[st[now][i-1]][i-1];for(int i=head[now];i;i=line[i].nxt)if(line[i].p!=fa)dfs(line[i].p,now); } int lca(int a,int b) {if(dep[a]<dep[b]) swap(a,b);for(int i=log[dep[a]];i>=0;i--)if(dep[st[a][i]]>=dep[b])a=st[a][i];if(a==b) return a;for(int i=log[dep[a]];i>=0;i--)if(st[a][i]!=st[b][i])a=st[a][i],b=st[b][i];return st[a][0]; } void DFS(int now,int fa) {int pas=0;for(int i=head[now];i;i=line[i].nxt)if(line[i].p!=fa){DFS(line[i].p,now);t[now]+=t[line[i].p];}ans=max(ans,t[now]); } int main() {int n,k;scanf("%d%d",&n,&k);for(int i=2;i<=n;i++) log[i]=log[i>>1]+1;int a,b;for(int i=1;i<n;i++){scanf("%d%d",&a,&b);add(a,b);add(b,a);}dfs(1,0);for(int i=1;i<=k;i++){scanf("%d%d",&a,&b);t[a]++;t[b]++;int LCA=lca(a,b);t[LCA]--; t[st[LCA][0]]--;}DFS(1,0);printf("%d",ans); }轉(zhuǎn)載于:https://www.cnblogs.com/Lance1ot/p/9403259.html
總結(jié)
以上是生活随笔為你收集整理的P3128 [USACO15DEC]最大流Max Flow的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
