Codechef 14.11 FNCS 分块
Codechef 14.3 GERALD07 LCT+可持久化线段树

Codechef 14.6 TWOCOMP 树链求交+网络流

shinbokuow posted @ Nov 20, 2015 04:12:54 PM in Something with tags 树链求交 网络流 , 551 阅读

 

题目大意:

给定一棵$n$个点的树,上面有$A,B$两种路径,每种路径不超过$m$条,其中每条路径都有一个权值。
现在可以在每种路径中各选出一些,使得$A$中被选中的任一条路径与$B$中被选中的任一条路径之间都没有交点,在此条件下最大化被选中的路径的权值之和。
数据范围$n\leq{10^5},m\leq{700}$。
算法讨论:
我们首先需要判断两条链之间有没有交点。
我们将链拆成两条(或一条)深度单调递减的路径,那么只需判定两条这样的路径是否有交即可。
不难发现,两条深度递增的路径有交,则必定有一条路径,其深度最小的点$x$在另一条路径上$(a,b)$。其中$a$表示另一条路径深度最小的点,$b$表示另一条路径深度最大的点。
那么只需判定是否满足$a$是$x$的祖先且$x$是$b$的祖先。
于是对两个点$x,y$,我们如何判定$x$是不是$y$的祖先呢?
我们显然可以预处理倍增数组,并倍增判断,但是存在更加优秀的算法。
我们对树进行DFS,预处理出每个点的入栈、出栈序,不妨记为$in_i,out_i$,则$x$是$y$的祖先当且仅当$in_x\leq{in_y}$且$out_x\geq{out_y}$。
这样的话,我们就能$O(1)$判定两条路径有没有交了。
我们枚举$A,B$的每条路径,若路径有交则将两条路径对应的点连边,我们能发现这个原问题其实就是一个二分图最大带权独立集问题,可以利用最大流解决。
时间复杂度为$O(n+m^2+m^4)$。
对于网络流问题,虽然时间复杂度的上界非常高,但一般不容易达到瓶颈,所以还是能够通过的。
时空复杂度:
时间复杂度$O(n+m^4)$,空间复杂度$O(n+m^2)$。
代码:
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define inf 1500000000
 
#define N 100010
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){
    static int q=1;
    end[q]=b;
    next[q]=head[a];
    head[a]=q++;
}
inline void make(int a,int b){
    addedge(a,b);
    addedge(b,a);
}
int dep[N],pa[N][21],in[N],out[N],tclock;
inline void dfs(int x,int fa){
    in[x]=++tclock;
    for(int j=head[x];j;j=next[j]){
        if(end[j]!=fa){
            dep[end[j]]=dep[x]+1;
            pa[end[j]][0]=x;
            dfs(end[j],x);
        }
    }
    out[x]=tclock;
}
inline int lca(int x,int y){
    if(dep[x]<dep[y])
        swap(x,y);
    for(int i=20;i>=0;--i)
        if(dep[pa[x][i]]>=dep[y])
            x=pa[x][i];
    if(x==y)
        return x;
    for(int i=20;i>=0;--i)
        if(pa[x][i]!=pa[y][i])
            x=pa[x][i],y=pa[y][i];
    return pa[x][0];
}
 
inline bool isanc(int son,int anc){
    return in[anc]<=in[son]&&out[anc]>=out[son];
}
inline bool onpath(int x,int down,int up){
    return isanc(down,x)&&isanc(x,up);
}
struct Path{
    int down[2],up[2],siz;
}A[710],B[710];
inline bool intersect(const Path&a,const Path&b){
    for(int i=0;i<a.siz;++i)
        for(int j=0;j<b.siz;++j){
            if(onpath(a.down[i],b.down[j],b.up[j]))
                return 1;
            if(onpath(a.up[i],b.down[j],b.up[j]))
                return 1;
            if(onpath(b.down[j],a.down[i],a.up[i]))
                return 1;
            if(onpath(b.up[j],a.down[i],a.up[i]))
                return 1;
        }
    return 0;
}
 
int wa[710],wb[710];
 
struct Solver{
    static const int V=1410;
    static const int E=2000010;
    int head[V],next[E],end[E],flow[E],ind;
    int d[V];
    inline void reset(){
        ind=0;
        memset(head,-1,sizeof head);
    }
    inline void addedge(int a,int b,int f){
        int q=ind++;
        end[q]=b;
        next[q]=head[a];
        head[a]=q;
        flow[q]=f;
    }
    inline void make(int a,int b,int f){
        addedge(a,b,f);
        addedge(b,a,0);
    }
    inline bool bfs(int s,int t){
        static int q[V];
        int fr=0,ta=0;
        memset(d,-1,sizeof d);
        d[s]=0;
        q[ta++]=s;
        while(fr!=ta){
            int i=q[fr++];
            for(int j=head[i];j!=-1;j=next[j])
                if(flow[j]&&d[end[j]]==-1)
                    d[q[ta++]=end[j]]=d[i]+1;
        }
        return d[t]!=-1;
    }
    inline int dinic(int p,int t,int Maxflow){
        if(p==t)
            return Maxflow;
        int last=Maxflow;
        for(int j=head[p];j!=-1;j=next[j]){
            if(flow[j]&&d[end[j]]==d[p]+1){
                int to=dinic(end[j],t,last>flow[j]?flow[j]:last);
                if(to){
                    flow[j]-=to;
                    flow[j^1]+=to;
                    if(!(last-=to))
                        return Maxflow;
                }
            }
        }
        d[p]=-1;
        return Maxflow-last;
    }
    inline int Maxflow(int s,int t){
        int re=0;
        while(bfs(s,t))
            re+=dinic(s,t,inf);
        return re;
    }
}g;
 
int main(){
    int n,m1,m2;
    cin>>n>>m1>>m2;
    int i,j,a,b;
    for(i=1;i<n;++i){
        scanf("%d%d",&a,&b);
        make(a,b);
    }
    dep[1]=1;
    dfs(1,-1);
    for(j=1;j<=20;++j)
        for(i=1;i<=n;++i)
            pa[i][j]=pa[pa[i][j-1]][j-1];
     
    int _lca;
    int ans=0;
    for(i=1;i<=m1;++i){
        scanf("%d%d%d",&a,&b,&wa[i]);
        ans+=wa[i];
        _lca=lca(a,b);
        if(_lca==a){
            A[i].siz=1;
            A[i].down[0]=b;
            A[i].up[0]=a;
        }
        else if(_lca==b){
            A[i].siz=1;
            A[i].down[0]=a;
            A[i].up[0]=b;
        }
        else{
            A[i].siz=2;
            A[i].down[0]=a;
            A[i].down[1]=b;
            A[i].up[0]=A[i].up[1]=_lca;
        }
    }
    for(i=1;i<=m2;++i){
        scanf("%d%d%d",&a,&b,&wb[i]);
        ans+=wb[i];
        _lca=lca(a,b);
        if(_lca==a){
            B[i].siz=1;
            B[i].down[0]=b;
            B[i].up[0]=a;
        }
        else if(_lca==b){
            B[i].siz=1;
            B[i].down[0]=a;
            B[i].up[0]=b;
        }
        else{
            B[i].siz=2;
            B[i].down[0]=a;
            B[i].down[1]=b;
            B[i].up[0]=B[i].up[1]=_lca;
        }
    }
     
    int s=0,t=m1+m2+1;
    g.reset();
    for(i=1;i<=m1;++i)
        g.make(s,i,wa[i]);
    for(i=1;i<=m2;++i)
        g.make(m1+i,t,wb[i]);
    for(i=1;i<=m1;++i)
        for(j=1;j<=m2;++j)
            if(intersect(A[i],B[j]))
                g.make(i,m1+j,inf);
     
    printf("%d\n",ans-g.Maxflow(s,t));
     
    return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter