OI题解 - ALT(Codeforces) | Lucky

~~#Lucky_Glass 鸽博客的日常#~~（不是）
这道题讲过好多次，以至于我以为我做过……结果到Codeforces一看，是WA的 QwQ

# 题意

一座城市有 $n$ 座楼，一些楼与楼之间有路连接，形成树形结构。每条路上都有一个警察，有一些警察会配备警犬。
一共有 $m$ 个居民，第 $i$ 个居民从楼 $x_i$ 出发，经过最短路径到达楼 $y_i$。有一些居民自带警犬。

居民有安全感当且仅当他自带警犬或他经过的所有路上的警察都配备警犬。
现要求分配尽可能少的警犬，使得每个居民都有安全感。

输出最小需要多少警犬、哪些居民自带警犬、哪些路上的警察配备警犬。

数据规模：$2\le n\le2\times10^4$; $1\le m\le10^4$。

# 解析

- 最小割 & 二分图

“要么是居民自带警犬，要么是他经过的路上都有警犬”这样的关系很容易想到最小割（在数据规模允许的前提下），也是一个非常经典的模型了。

把每个居民、每条路建点。S 向每个居民连容量为 $1$ 的边，每条路向 T 连容量为 $1$ 的边；每个居民向他要经过的所有路连容量为 $+\infty$ 的边。

跑一遍最小割：如果 S 到居民 i 的边被割掉，则居民 i 自带警犬；如果路 i 到 T 的边被割掉，则路 i 的警察配备警犬。（因为居民与路之间是 $+\infty$ 的边，不可能被割掉）

- 线段树优化建图 & 树链剖分

这样建图，点数 $O(n+m)$，完全没有问题，但是边数是 $O(n+m+nm)$，完全不行。于是想到平衡点数和边数——

在一条数轴上，给连续的一段区间的每个点连边，常用的方法就是线段树优化建图。换到树上是否可以呢？因为树链剖分的正确性显然，而且“路径”就意味着在树上是连续的一段，所以也是没有问题的。

而且这道题比较特别的是，由于树上的每个点（也就是二分图中表示路的点）的出边只有连向 T 的边，所以没有必要给出点和入点分别建树，只建入点的线段树即可。这样的话，只需要把线段树的每个叶子连向 T 即可。

现在点数 $O(m+2n)$，边数 $O(n+m+m\log n)$，没有什么问题。

- 输出方案

算是这道题的难点了。虽然最小割的大小可以直接跑最大流，但是最小割的方案却与最大流没什么关系。只能构造一个特殊解。

最先想到的一定是最大流中满流的边。的确有这样一个性质：最小割的边一定满流（因为最小割=最大流）。但是并不是所有满流的边都是最小割的边。

如果我们把所有满流的边删去，得到若干连通块，那么 S 和 T 一定在不同的块里（否则还可以增广，不满足最大流性质）。于是可以直接把 S 所在的连通块作为最小割切割后的 “S部”，剩下的作为 “T部”，就构造出一个特殊解了。

> 正确性：

首先 S部与 T部之间的边是一个割集。
然后因为 S部与 T部之间的边是满流的边，所以这些满流的边的流量之和为最大流（把图画出来就可以发现了），也就是最小割。

# 源代码

/*Lucky_Glass*/
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=2e4,M=1e4,INF=(1<<29),SZ=2*N+M+10;

vector< pair<int,int> > tre[N+3];
int n,m,S,T,ndfn,nsiz;
int idfn[N+3],dfn[N+3],fa[N+3],top[N+3],hvy[N+3],siz[N+3],dep[N+3];
int dis[SZ],le[2*N+3],ri[2*N+3],ans1[N+3],ans2[M+3],prt[N+3];
bool vis[SZ];

struct EDGE{
    int to,cap;
    EDGE *nxt,*rev;
    EDGE(){}
    EDGE(int _t,int _c,EDGE *_n,EDGE *_r):to(_t),cap(_c),nxt(_n),rev(_r){}
};
struct GRAPH{
    EDGE edg[(2*N*2+M*30)*2],*head[SZ],*ncnt;
    GRAPH(){ncnt=edg;}
    void AddEdge(int u,int v,int cap){
        // printf("add %d %d %d\n",u,v,cap);
        EDGE *p=++ncnt,*q=++ncnt;
        *p=EDGE(v,cap,head[u],q);head[u]=p;
        *q=EDGE(u,  0,head[v],p);head[v]=q;
    }
    EDGE* operator [](int id){return head[id];}
};
GRAPH Gr;
EDGE *cop[SZ];

namespace SEG{
    inline int Index(int lef,int rig){return (lef+rig)|(lef!=rig);}
    void Build(int lef,int rig){
        int u=Index(lef,rig);
        le[u]=lef;ri[u]=rig;
        if(lef==rig){
            Gr.AddEdge(u,T,1);
            return ;
        }
        int mid=(lef+rig)>>1;
        Gr.AddEdge(u,Index(lef,mid),INF);
        Gr.AddEdge(u,Index(mid+1,rig),INF);
        Build(lef,mid);Build(mid+1,rig);
    }
    void Add(int lef,int rig,int Le,int Ri,int u){
        if(Le>Ri) return;
        int v=Index(lef,rig);
        if(Le<=lef && rig<=Ri){
            Gr.AddEdge(u,v,INF);
            return;
        }
        int mid=(lef+rig)>>1;
        if(Le<=mid) Add(lef,mid,Le,Ri,u);
        if(Ri>mid) Add(mid+1,rig,Le,Ri,u);
    }
}
void DFS1(int u){
    // printf("u=%d\n",u);
    siz[u]=1;
    for(int i=(int)tre[u].size()-1;i>=0;i--){
        int v=tre[u][i].first;
        if(v==fa[u]) continue;
        prt[v]=tre[u][i].second;
        fa[v]=u;dep[v]=dep[u]+1;
        DFS1(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[hvy[u]]) hvy[u]=v;
    }
}
void DFS2(int u,int to){
    dfn[u]=++ndfn;idfn[dfn[u]]=u;top[u]=to;
    if(hvy[u]) DFS2(hvy[u],to);
    else return;
    for(int i=(int)tre[u].size()-1;i>=0;i--){
        int v=tre[u][i].first;
        if(v==hvy[u] || v==fa[u]) continue;
        DFS2(v,v);
    }
}
void Road(int u,int v,int from){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        SEG::Add(1,n,dfn[top[u]],dfn[u],from);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    SEG::Add(1,n,dfn[v]+1,dfn[u],from);
}
void AddEdge(int u,int v,int id){
    tre[u].push_back(make_pair(v,id));
    tre[v].push_back(make_pair(u,id));
}
int Aug(int u,int in){
    if(u==T) return in;
    int out=0;
    while(cop[u]){
        EDGE *it=cop[u];cop[u]=cop[u]->nxt;
        int v=it->to;
        if(it->cap<=0 || dis[u]+1!=dis[v]) continue;
        int tov=Aug(v,min(it->cap,in-out));
        out+=tov;
        it->cap-=tov;it->rev->cap+=tov;
        if(out==in) break;
    }
    return out;
}
bool BFS(){
    for(int i=1;i<=nsiz;i++) dis[i]=-1,cop[i]=Gr[i];
    queue<int> que;que.push(S);
    dis[S]=0;
    while(!que.empty()){
        int u=que.front();que.pop();
        for(EDGE *it=Gr[u];it;it=it->nxt){
            int v=it->to;
            if(dis[v]!=-1 || it->cap<=0) continue;
            // printf("%d -> %d\n",u,v);
            dis[v]=dis[u]+1;
            if(v==T) return true;
            que.push(v);
        }
    }
    return false;
}
int Dinic(){
    int res=0;
    while(BFS()) res+=Aug(S,INF);
    return res;
}
void DFS3(int u){
    vis[u]=true;
    for(EDGE *it=Gr[u];it;it=it->nxt)
        if(it->cap>0 && !vis[it->to])
            DFS3(it->to);
}
int main(){
    // freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&m);
    S=2*n+1;T=S+1;
    for(int i=1,u,v;i<n;i++)
        scanf("%d%d",&u,&v),
        AddEdge(u,v,i);
        // printf("okey");
    dep[1]=1;DFS1(1);DFS2(1,1);
    SEG::Build(1,n);
    for(int i=1;i<=m;i++){
        int x,y;scanf("%d%d",&x,&y);
        int u=T+i;
        Gr.AddEdge(S,u,1);
        Road(x,y,u);
    }
    nsiz=T+m;
    printf("%d\n",Dinic());
    DFS3(S);
    for(int i=1;i<=nsiz;i++){
        if(i==S || i==T || !vis[i]) continue;
        if(i<=2*n){
            int lef=le[i],rig=ri[i];
            ans1[lef]++;ans1[rig+1]--;
        }
        else
            ans2[i-T]=1;
    }
    int tot1=0,tot2=0;
    for(int i=1;i<=m;i++){
        if(ans2[i]) continue;
        tot1++;
    }
    printf("%d",tot1);
    for(int i=1;i<=m;i++){
        if(ans2[i]) continue;
        printf(" %d",i);
    }
    printf("\n");
    for(int i=1;i<=n;i++){
        ans1[i]+=ans1[i-1];
        if(!ans1[i]) continue;
        tot2++;
    }
    printf("%d",tot2);
    for(int i=1;i<=n;i++){
        if(!ans1[i]) continue;
        printf(" %d",prt[idfn[i]]);
    }
    printf("\n");
    return 0;
}

The End

Thanks for reading!

把这篇博客写完我就可以咕了！