洛谷 P3128 [USACO15DEC]最大流Max Flow

题目描述

Farmer John has installed a new system of $N-1$ pipes to transport milk between the $N$ stalls in his barn ( $2 leq N leq 50,000$ ), conveniently numbered $1 ldots N$ . Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.

FJ is pumping milk between $K$ pairs of stalls ( $1 leq K leq 100,000$ ). For the $i$ th such pair, you are told two stalls $s_i$ and $t_i$ , endpoints of a path along which milk is being pumped at a unit rate. FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the $K$ paths along which milk is being pumped. Please help him determine the maximum amount of milk being pumped through any stall. If milk is being pumped along a path from $s_i$ to $t_i$ , then it counts as being pumped through the endpoint stalls $s_i$ and

$t_i$ , as well as through every stall along the path between them.

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 $N$ and $K$ .

The next $N-1$ lines each contain two integers $x$ and $y$ ( $x e 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.

输出格式：

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

barn.

输入输出样例

输入样例#1：

输出样例#1：

9


解法一：
裸树剖
dfs写丑了 T了6次
屠龙宝刀点击就送

#include <ctype.h>
#include <cstdio> 
#define M 100005
#define N 50005

void read(int &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    x=f?(~x)+1:x;
}
struct Edge
{
    int next,to;
    Edge (int next=0,int to=0) :next(next),to(to){}
}edge[M<<1];
struct Tree
{
    int l,r,dis,flag;
    Tree *left,*right;
    Tree()
    {
        left=right=NULL;
        dis=flag=0; 
    }
}*root;
int end[N],top[N],size[N],belong[N],dep[N],tim,fa[N],n,k,head[N],cnt;
void add(int u,int v)
{
    edge[++cnt]=Edge(head[u],v);
    head[u]=cnt;
}
void dfs1(int x)
{
    size[x]=1;
    dep[x]=dep[fa[x]]+1;
    for(int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(fa[x]!=v)
        {
            fa[v]=x;
            dfs1(v);
            size[x]+=size[v];
        }
    }
}
void dfs2(int x)
{
    int t=0;
    if(!top[x]) top[x]=x;
    belong[x]=++tim;
    for(int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(fa[x]!=v&&size[t]<size[v]) v=t;
    }
    if(t) top[t]=top[x],dfs2(t);
    else end[x]=tim;
    for(int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(fa[x]!=v&&v!=t) dfs2(v);
    }
    end[x]=tim;
}
int max(int a,int b) {return a>b?a:b;} 
void build(Tree *&k,int l,int r)
{
    k=new Tree;
    k->l=l;k->r=r;
    if(l==r)
    {
        k->dis=0;
        return;
    }
    int mid=(l+r)>>1;
    build(k->left,l,mid);
    build(k->right,mid+1,r);
    k->dis=k->left->dis+k->right->dis;
}
void swap(int &x,int &y) 
{
    int tmp=y;
    y=x;
    x=tmp;
}
void pushdown(Tree *&k)
{
    if(k->l==k->r) return;
    k->left->flag+=k->flag;
    k->right->flag+=k->flag;
    k->left->dis+=k->flag;
    k->right->dis+=k->flag;
    k->flag=0;
}
void Tree_change(Tree *&k,int l,int r)
{
    if(k->l==l&&k->r==r)
    {
        k->dis++;
        k->flag++;
        return;
    }
    if(k->flag) pushdown(k);
    int mid=(k->l+k->r)>>1;
    if(l>mid) Tree_change(k->right,l,r);
    else if(r<=mid) Tree_change(k->left,l,r);
    else Tree_change(k->left,l,mid),Tree_change(k->right,mid+1,r);
    k->dis=max(k->left->dis,k->right->dis);
}
void Chain_change(int x,int y)
{
    for(;top[x]!=top[y];x=fa[top[x]])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        Tree_change(root,belong[top[x]],belong[x]); 
    }
    if(dep[x]<dep[y]) swap(x,y);
    Tree_change(root,belong[y],belong[x]);
}
int Tree_query(Tree *&k,int l,int r)
{
    if(k->l==l&&k->r==r) return k->dis;
    if(k->flag) pushdown(k);
    int mid=(k->l+k->r)>>1;
    if(l>mid) return Tree_query(k->right,l,r);
    else if(r<=mid) return Tree_query(k->left,l,r);
    else return max(Tree_query(k->left,l,mid),Tree_query(k->right,mid+1,r));
    k->dis=max(k->left->dis,k->right->dis);
}
int main()
{
    read(n);
    read(k);
    for(int x,y,i=1;i<n;i++)
    {
        read(x);read(y);
        add(x,y);
        add(y,x);
    }
    dfs1(1);
    dfs2(1);
    root=new Tree;
    build(root,1,n);
    for(int x,y;k--;)
    {
        read(x);read(y);
        Chain_change(x,y);
    }
    printf("%d
",Tree_query(root,belong[1],end[1]));
    return 0;
}

蜜汁TLE代码求改

#include <ctype.h>
#include <cstdio> 
#define M 50005

void read(int &x)
{
    x=0;register bool f=0;
    register char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    x=f?(~x)+1:x;
}
struct Edge
{
    int next,to;
    Edge (int next=0,int to=0) :next(next),to(to){}
}edge[M<<2];
struct Tree
{
    int mid,l,r,dis,flag;
}tr[M<<4];
int tot,end[M],top[M],size[M],belong[M],dep[M],tim,dad[M],n,k,head[M],cnt;
inline void add(int u,int v)
{
    edge[++cnt]=Edge(head[u],v);
    head[u]=cnt;
}
inline void dfs1(int x,int fa)
{
    int pos=tot++;
    dad[x]=fa;
    dep[x]=dep[fa]+1;
    for(int i=head[x];i;i=edge[i].next)
    {
        if(edge[i].to==fa) continue;
        dfs1(edge[i].to,x);
    }
    size[x]=tot-pos;
}
inline void dfs2(int x,int chain)
{
    belong[x]=++tim;
    top[x]=chain;
    int pos=0;
    for(int i=head[x];i;i=edge[i].next)
    {
        if(edge[i].to==dad[x]) continue;
        if(size[edge[i].to]>size[pos]) pos=edge[i].to;
    }
    if(pos==0) return;
    dfs2(pos,chain);
    for(int i=head[x];i;i=edge[i].next)
    {
        if(edge[i].to==dad[x]||edge[i].to==pos) continue;
        dfs2(edge[i].to,edge[i].to);
    }
}
inline int max(int a,int b) {return a>b?a:b;} 
inline void build(int k,int l,int r)
{
    tr[k].l=l;tr[k].r=r;
    if(l==r) return;
    tr[k].mid=(l+r)>>1;
    build(k<<1,l,tr[k].mid);
    build(k<<1|1,tr[k].mid+1,r);
}
inline void swap(int &x,int &y) 
{
    register int tmp=y;
    y=x;
    x=tmp;
}
inline void pushdown(int k)
{
    if(tr[k].l==tr[k].r) return;
    tr[k<<1].flag+=tr[k].flag;
    tr[k<<1|1].flag+=tr[k].flag;
    tr[k<<1].dis+=tr[k].flag;
    tr[k<<1|1].dis+=tr[k].flag;
    tr[k].flag=0;
}
inline void Tree_change(int k,int l,int r)
{
    if(tr[k].l==l&&tr[k].r==r)
    {
        tr[k].dis++;
        tr[k].flag++;
        return;
    }
    if(tr[k].flag) pushdown(k);
    if(l>tr[k].mid) Tree_change(k<<1|1,l,r);
    else if(r<=tr[k].mid) Tree_change(k<<1,l,r);
    else Tree_change(k<<1,l,tr[k].mid),Tree_change(k<<1|1,tr[k].mid+1,r);
    tr[k].dis=max(tr[k<<1].dis,tr[k<<1|1].dis);
}
inline void Chain_change(int x,int y)
{
    for(;top[x]!=top[y];x=dad[top[x]])
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        Tree_change(1,belong[top[x]],belong[x]); 
    }
    if(dep[x]<dep[y]) swap(x,y);
    Tree_change(1,belong[y],belong[x]);
}
int main(int argc,char *argv[])
{
    read(n);read(k);
    for(register int x,y,i=1;i<n;i++)
    {
        read(x);read(y);
        add(x,y);
        add(y,x);
    }
    dfs1(1,0);
    dfs2(1,1);
    build(1,1,n);
    for(register int x,y;k--;)
    {
        read(x);read(y);
        Chain_change(x,y);
    }
    printf("%d
",tr[1].dis);
    return 0;
}

解法二：

树上差分+倍增LCA
其实此题树剖LCA更快
但本弱鸡只觉得倍增好看 。。

#include <ctype.h>
#include <cstdio> 
#define M 50005

void read(int &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    x=f?(~x)+1:x;
}
struct Edge
{
    int next,to;
}edge[M<<2];
int ans,dis[M<<1],head[M<<2],cnt,dad[M][25],dep[M],n,k;
void add(int u,int v)
{
    edge[++cnt].next=head[u];
    edge[cnt].to=v;
    head[u]=cnt;
}
void dfs(int x)
{
    dep[x]=dep[dad[x][0]]+1;
    for(int i=0;dad[x][i];i++)
    dad[x][i+1]=dad[dad[x][i]][i];
    for(int i=head[x];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(dad[x][0]!=v)
        {
            dad[v][0]=x;
            dfs(v);
        }
    }
}
void swap(int &x,int &y)
{
    int tmp=y;
    y=x;
    x=tmp;
}
int lca(int x,int y)
{
    if(dep[x]>dep[y]) swap(x,y);
    for(int i=20;i>=0;i--)
    if(dep[dad[y][i]]>=dep[x]) y=dad[y][i];
    if(y==x) return x;
    for(int i=20;i>=0;i--)
    if(dad[x][i]!=dad[y][i]) x=dad[x][i],y=dad[y][i];
    return dad[x][0];
}
int max(int a,int b) {return a>b?a:b;}
void dfs2(int x)
{
    for(int u=head[x];u;u=edge[u].next)
    {
        int v=edge[u].to;
        if(dad[x][0]!=v)
        {
            dfs2(v);
            dis[x]+=dis[v];
        }
    }
    ans=max(ans,dis[x]);
}
int main()
{
    read(n);
    read(k);
    for(int x,y,i=1;i<n;i++)
    {
        read(x);
        read(y);
        add(x,y);
        add(y,x);
    }
    dfs(1);
    for(int x,y;k--;)
    {
        read(x);read(y);
        dis[x]++;dis[y]++;
        int Lca=lca(x,y);
        dis[Lca]--;dis[dad[Lca][0]]--;
    }
    dfs2(1);
    printf("%d",ans);
}

我们都在命运之湖上荡舟划桨，波浪起伏着而我们无法逃脱孤航。但是假使我们迷失了方向，波浪将指引我们穿越另一天的曙光。