P3128 [USACO15DEC] 最大流 Max Flow#
題面#
題目描述#
FJ 給他的牛棚的 N (2≤N≤50,000) 個隔間之間安裝了 N-1 根管道，隔間編號從 1 到 N。所有隔間都被管道連通了。
FJ 有 K (1≤K≤100,000) 條運輸牛奶的路線，第 i 條路線從隔間 si 運輸到隔間 ti。一條運輸路線會給它的兩個端點處的隔間以及中間途徑的所有隔間帶來一個單位的運輸壓力，你需要計算壓力最大的隔間的壓力是多少。
輸入輸出格式#
輸入格式：#
The first line of the input contains NNN and KKK.
The next N?1N-1N?1 lines each contain two integers xxx and yyy (x≠yx \ne yx≠y) describing a pipe
between stalls xxx and yyy.
The next KKK lines each contain two integers sss and ttt describing the endpoint
stalls of a path through which milk is being pumped.
輸出格式：#
An integer specifying the maximum amount of milk pumped through any stall in the barn.
輸入輸出範例#
輸入範例 #1：
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
輸出範例 #1：
9
Solve#
樹上差分模板題。
好難，做了一下午
（樹咋存來著？）
一開始覺得前向星來存樹不好找爸爸。折騰了半天還是用了前向星。
然後 LCA 也忘了。我還非常沙雕地用 tarjan 求出每兩個點之間的 LCA，還開小了數組。結果 TLE+MLE。
改用倍增求一直不過範例，後來才發現我一直用的存父親的數組是放在 tarjan LCA 裡求的。。。
接著只過了一兩個點的原因竟然是：
int getLca(int p1,int p2) {
if(depth[p1]<depth[p2]){p1^=p2;p2^=p1;p1^=p2;}
for(int i=H;i>=0;--i){
if(depth[f[p1][i]]>=depth[p2])p1=f[p1][i];}
if(p1==p2)return p1;
for(int i=H;i>=0;--i)
if(f[p1][i]!=f[p2][i]){
p1=f[p1][i];
p2=f[p2][i];}
/*沒錯就是這裡！！！！！*/
return p1;
//應該是return f[p1][0];
}
差錯的時候寫了 dfs 和 bfs 兩種初始化方法，現在都能 AC。
完整代碼如下
#include<cstdio>
#include<iostream>
#include<utility>
#include<map>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=2e5+5;
struct ed
{
int to,nex,w;
} e[MAXN];
int head[MAXN];
int dad[MAXN];//樹的
bool v[MAXN];
int yaLi[MAXN];
int depth[MAXN];//深度
int f[MAXN][16];//for 倍增
int H;
int maxYaLi=0;
int root=1,newp;
map<pair<int,int>,int> zuzong;
int n,k;
void vAdd(int x,int y);
void doUnion(int x,int y);
void doInit(void);
void lca(int p);
void getMax(int p);
void bfs(int root);
void dfs(int p,int fat);
int doFind(int x);
int readLca(int p1,int p2);
int getLca(int p1,int p2);
int main(void)
{
scanf("%d%d",&n,&k);
H=1.0*log(n)/log(2);
for(int i=1;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
vAdd(x,y);
vAdd(y,x);
}
bfs(1);
//或dfs(1,0);
for(int i=1;i<=k;++i)
{
int x,y;
scanf("%d%d",&x,&y);
int lca=getLca(x,y);
++yaLi[x];
++yaLi[y];
--yaLi[lca];
--yaLi[f[lca][0]];
}
memset(v,0,sizeof(v));
getMax(1);
printf("%d\n",maxYaLi);
return 0;
}
void vAdd(int x,int y)
{
++newp;
e[newp].to=y;
e[newp].nex=head[x];
head[x]=newp;
}
void getMax(int p)
{
v[p]=1;
for(int i=head[p];i;i=e[i].nex)
{
int y=e[i].to;
if(v[y])continue;
else
{
getMax(y);
yaLi[p]+=yaLi[y];
}
}
maxYaLi=max(maxYaLi,yaLi[p]);
}
int getLca(int p1,int p2)
{
if(depth[p1]<depth[p2])
{
p1^=p2;//交換值
p2^=p1;
p1^=p2;
}
for(int i=H;i>=0;--i)
{
if(depth[f[p1][i]]>=depth[p2])
{
p1=f[p1][i];
}
}
if(p1==p2)return p1;
for(int i=H;i>=0;--i)
{
if(f[p1][i]!=f[p2][i])
{
p1=f[p1][i];
p2=f[p2][i];
}
}
return f[p1][0];
}
#include<queue>
void bfs(int root)
{
queue<int> q;
q.push(root);
depth[root]=1;
v[root]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nex)
{
int y=e[i].to;
if(v[y])continue;
else
{
v[y]=1;
depth[y]=depth[u]+1;
f[y][0]=u;
for(int j=1;j<=H;++j)
{
f[y][j]=f[f[y][j-1]][j-1];
}
q.push(y);
}
}
}
}
void dfs(int p,int fat)
{
depth[p]=depth[fat]+1;
f[p][0]=fat;
for(int i=1;i<=H;++i)
{
f[p][i]=f[f[p][i-1]][i-1];
}
for(int i=head[p];i;i=e[i].nex)
{
int y=e[i].to;
if(y==fat)continue;
else dfs(y,p);
}
}
還有一份 41 分代碼（Tarjan）
#include<cstdio>
#include<iostream>
#include<utility>
#include<map>
#include<cstring>
using namespace std;
const int MAXN=5e4+5;
struct ed
{
int to,nex,w;
} e[MAXN];
int head[MAXN];
int fa[MAXN];//並查集的
int dad[MAXN];//樹的
bool v[MAXN];
int yaLi[MAXN];
int maxYaLi=0;
int root=1,newp;
map<pair<int,int>,int> zuzong;
int n,k;
void vAdd(int x,int y);
void doUnion(int x,int y);
void doInit(void);
int doFind(int x);
void lca(int p);
int readLca(int p1,int p2);
void getMax(int p);
int main(void)
{
scanf("%d%d",&n,&k);
doInit();
for(int i=1;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
vAdd(x,y);
vAdd(y,x);
}
lca(1);
for(int i=1;i<=k;++i)
{
int x,y;
scanf("%d%d",&x,&y);
int lca=readLca(x,y);
++yaLi[x];
++yaLi[y];
--yaLi[lca];
--yaLi[dad[lca]];
}
memset(v,0,sizeof(v));
getMax(1);
printf("%d\n",maxYaLi);
return 0;
}
void vAdd(int x,int y)
{
++newp;
e[newp].to=y;
e[newp].nex=head[x];
head[x]=newp;
}
void doInit(void)
{
for(int i=1;i<=n;++i)
{
fa[i]=i;
}
}
void doUnion(int x,int y)
{
x=doFind(x);
y=doFind(y);
fa[x]=y;
}
int doFind(int x)
{
if(fa[x]==x)return x;
else return fa[x]=doFind(fa[x]);
}
void lca(int u)
{
v[u]=1;
for(int i=head[u];i;i=e[i].nex)
{
int y=e[i].to;
if(v[y])continue;
else
{
dad[y]=u;
lca(y);
doUnion(y,u);
}
}
for(int i=1;i<=n;++i)
{
if(i==u)continue;
else
{
if(v[i])
{
zuzong[make_pair(u,i)]=doFind(i);
}
}
}
}
int readLca(int p1,int p2)
{
pair<int,int> pa=make_pair(p1,p2),pb=make_pair(p2,p1);
int z1=zuzong[pa];
if(z1)return z1;
else return zuzong[pb];
}
void getMax(int p)
{
v[p]=1;
for(int i=head[p];i;i=e[i].nex)
{
int y=e[i].to;
if(v[y])continue;
else
{
getMax(y);
yaLi[p]+=yaLi[y];
}
}
maxYaLi=max(maxYaLi,yaLi[p]);
}