Codechef 14.6 TWOCOMP 树链求交+网络流
题目大意:
给定一棵$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; }