Luogu P3128 Max Flow - BuringStraw

P3128 [USACO15DEC] Max Flow#

Problem Description#

FJ has installed N (2≤N≤50,000) pipes between the N-1 stalls in his cowshed, numbered from 1 to N. All stalls are connected by pipes.

FJ has K (1≤K≤100,000) milk transportation routes. The i-th route transports milk from stall si to stall ti. A transportation route will bring one unit of transportation pressure to the stalls at its two endpoints and all the stalls in between. You need to calculate the maximum pressure among all the stalls.

Input and Output#

Input:#

The first line of the input contains N and K.

The next N-1 lines each contain two integers x and y (x≠y) describing a pipe between stalls x and y.

The next K lines each contain two integers s and t describing the endpoint stalls of a path through which milk is being pumped.

Output:#

An integer specifying the maximum amount of milk pumped through any stall in the barn.

Input and Output Examples#

Input Example #1:

Output Example #1:

Solve#

Tree Difference template problem.

~~It's difficult, took me the whole afternoon~~

~~(How do I store the tree again?)~~

At first, I thought it would be difficult to find the parent using the forward star method. After struggling for a while, I still used the forward star method.

Then I forgot about LCA. I even used Tarjan to find the LCA between every two points, and the array was too small. As a result, it resulted in TLE+MLE.

TLE+MLE

I changed to using doubling to find the LCA, but it still didn't pass the test cases. Later, I found out that I was using the array storing the parent in the Tarjan LCA...

Then the reason why it only passed one or two points was actually:

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];}
    /*The mistake is here!!!!*/
    return p1;
    //It should be return f[p1][0];
}

When there was an error, I wrote two initialization methods, dfs and bfs, and now both can pass.

The complete code is as follows:

#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];//tree
bool v[MAXN];
int yaLi[MAXN];

int depth[MAXN];//depth
int f[MAXN][16];//for doubling
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);
    //or 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;//swap values 
        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);
    }
}

There is also a 41-point code (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];//union-find set
int dad[MAXN];//tree
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]);
}