P3128 [USACO15DEC] 最大流 Max Flow#
题面#
题目描述#
FJ は彼の牛舎の N (2≤N≤50,000) 個の隔間の間に N-1 本のパイプを設置し、隔間の番号は 1 から N までです。すべての隔間はパイプで接続されています。
FJ は K (1≤K≤100,000) 本の牛乳を運ぶルートを持っており、第 i 本のルートは隔間 si から隔間 ti に運ばれます。1 本の運送ルートはその 2 つの端点の隔間と中間を通るすべての隔間に 1 単位の運送圧力を与えます。最大の圧力を持つ隔間の圧力を計算する必要があります。
入力出力形式#
入力形式：#
入力の最初の行には NNN と KKK が含まれています。
次の N-1 行にはそれぞれ 2 つの整数 xxx と yyy (x≠y) が含まれ、隔間 xxx と yyy の間のパイプを説明します。
次の KKK 行にはそれぞれ 2 つの整数 sss と ttt が含まれ、牛乳がポンプで送られる経路の端点隔間を説明します。
出力形式：#
牛舎内の任意の隔間を通過する牛乳の最大量を指定する整数。
入力出力サンプル#
入力サンプル #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 を使って 2 点間の LCA を求めて、配列を小さくしてしまった。結果は TLE+MLE。
倍増を使ってもサンプルを通過できず、後で気づいたのは、ずっと使っていた親を保存する配列が tarjan LCA で求めたものでした。。。
次に、1 つか 2 つの点しか通過できなかった理由は実際には：
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 の 2 つの初期化方法を書いたが、今はすべて 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];//倍増用
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);
}
}
もう 1 つの 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]);
}