P3128 [USACO15DEC]Max Flow P

P3128 [USACO15DEC]Max Flow P
树上差分之点差分模板题

题目描述：

FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。

FJ有K(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

题解：

树上差分 分为 点差分 和 边差分
点差分：

比如讲红色到绿色路径上的点都+x，求差分数组那么我们就对红色点和绿色点分别加上x，对黄色点减x，对黄色点的父亲节点减x。为什么呢？点差分求和时是从叶子节点开始往根上并，因为我们红绿都加x，合并时黄色就会加两个x（一个来自左边，一个右边），所以黄色要减x，为了避免影响到其他路径，所以黄色节点的父亲节点要减x，其实跟数组的差分本质也是一样的

边差分：

同样是对红色到绿色的路径加x，我们要在黄色点处减2x，这样就使得加x的效果只局限在u…v，不会向lca(u,v)的爸爸蔓延。这是边的累加情况，仔细考虑考虑

黄色点是红和绿的lca，所以还要用到lca算法

代码：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } int siz; const int maxn=5e4+9; vector<int>edge[maxn]; int fa[maxn][30],dep[maxn],dt[maxn]; void dfs(int x) {for(int i=1;i<=siz;i++){fa[x][i]=fa[fa[x][i-1]][i-1];}for(int i=0;i<edge[x].size();i++){int v=edge[x][i];if(v!=fa[x][0]){fa[v][0]=x;dep[v]=dep[x]+1;dfs(v);}} } int LCA(int u,int v) {if(dep[u]<dep[v])swap(u,v);int de=dep[u]-dep[v];for(int x=0;x<=siz;x++){if((1<<x)&de)u=fa[u][x];}if(u==v)return u;for(int x=siz;x>=0;x--){if(fa[u][x]!=fa[v][x]){u=fa[u][x];v=fa[v][x];}} return fa[u][0]; } int ans=0; void dfs_cnt(int x) {for(int i=0;i<edge[x].size();i++){int v=edge[x][i];if(v!=fa[x][0]){dfs_cnt(v);dt[x]+=dt[v];}ans=max(ans,dt[x]);} } int main() {int n,m;cin>>n>>m;siz=log2(n);for(int i=1;i<n;i++){int x,y;cin>>x>>y;edge[x].push_back(y);edge[y].push_back(x);}dfs(1);for(int i=1;i<=m;i++){int x,y;cin>>x>>y;int z=LCA(x,y);dt[z]--;dt[fa[z][0]]--;dt[x]++;dt[y]++;}dfs_cnt(1);cout<<ans<<endl;return 0; }

总结

以上是生活随笔为你收集整理的P3128 [USACO15DEC]Max Flow P的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。