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;
}
评论 (0)