P7520 [省选联考 2021 A 卷] 支配解题报告

解题报告

P7520 [省选联考 2021 A 卷] 支配

更好的阅读体验

题意

定义一个点$x$支配另一个点$y$当且仅当结点$1$到达结点$y$的每一条路径都要经过$x$，且点$y$的受支配集$D_y$为所有支配$y$的$x$形成的集合。

给定一个$n$个点$m$条边的图$G$，进行$q$次相互独立的询问，每次询问加入边$(x,y)$后有多少个点的受支配集有变化。

$1\leqslant n\leqslant 3000,1\leqslant m\leqslant 2\times n,1\leqslant q\leqslant 2\times 10^4$。

分析

似乎是支配树裸题，但我不会支配树/kk。

当我们不知道支配树时，应该怎么想到支配树呢？

考虑$1$到结点$x$的所有路径一定是不断“扩张”然后不断“收束”到一个点上，然后继续“扩张”与“收束”的一个过程，而每次“收束”到的点都是$x$的支配点。

不难发现除了结点$1$外任意结点$x$都有且仅有一个极大支配点$fa_x=y$，也就是说$D_x=D_y\cup\{x\}$，那么如果我们将$x$与$y$连一条边的话，根据支配的定义一定不会形成环，那么就会形成一个$n$个结点，$n-1$条边的无向无环联通图——支配树。

如何建出支配树呢？这里介绍一种$O(n^2)$的简单做法。

考虑设$delp_{x,y}$表示删除结点$x$后，结点$1$是否能到达结点$y$，那么我们只需要枚举$x$，然后每次$\text{dfs}$就可以$O(n^2)$的求出这个数组了。

又由于$delp_{x,y}=0$与$x$支配$y$等价，因此我们可以求出所有结点的受支配集。

那么我们对于每个点枚举它受支配集中每一个点，按照极大支配点的定义进行判断就好了。

建出支配树，又怎么求解呢？（设加入的边为$(u,v)$）

对于每一个点$x$，不难发现它的受支配集会改变当且仅当$fa_x$的受支配集改变或者$fa_x$不再支配$x$。（由极大支配点的定义可得）

那么我们从上到下遍历支配树（不要直接遍历，最好用$dfs$序或者$bfs$序，本文使用$bfs$序，也就是所有点按照支配集大小进行排序的结果），问题转化为判断一个点的极大支配点$fa_x$是否还支配$x$。

很容易发现支配树的支配关系是等价于原图的（这也是CCF设置图是一个树这个部分分的原因），那么我们只需要判断删除$x$的父亲从$1$是否能到达$u$，而$v$是否能到达$x$就好了。

那么我们再$O(n^2)$预处理一个$delf_{x,y}$表示删除$x$的父亲后$y$是否能到达$x$就做完这道题了。

时间复杂度：$O(n(n+q))$。

代码

被卡常了，交换了$delp_{x,y}$与$delf_{x,y}$定义中的$x$与$y$才能过。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=3005;
int n,m,q,e;
int bfn[maxn],fa[maxn],t[maxn],ok[maxn];
int delp[maxn][maxn],delf[maxn][maxn];//delp[y][x]: del x 1 to y ; delf[y][x]: del fa[x] 1 to y
vector<int>g[maxn],rg[maxn],d[maxn];
inline int cmp(int x,int y){
    return d[x].size()<d[y].size();
}
void getdelp(int x,int p){
    if(x==p)
        return ;
    delp[x][p]=1;
    for(int i=0;i<g[x].size();i++){
        int y=g[x][i];
        if(delp[y][p]==0)
            getdelp(y,p);
    }
}
void getdelf(int x,int p){
    if(x==fa[p])
        return ;
    delf[x][p]=1;
    for(int i=0;i<rg[x].size();i++){
        int y=rg[x][i];
        if(delf[y][p]==0)
            getdelf(y,p);
    }
}
void read(int &x){
    x=0;
    char c=getchar();
    for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+c-48;
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++){
        int x,y;
        read(x),read(y);
        g[x].push_back(y),rg[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        getdelp(1,i);
        for(int j=1;j<=n;j++)
            if(delp[j][i]==0)
                d[j].push_back(i);
    }
    for(int i=2;i<=n;i++)
        for(int j=0;j<d[i].size();j++)
            if(d[d[i][j]].size()==d[i].size()-1){
                fa[i]=d[i][j];
                break;
            }
    for(int i=1;i<=n;i++)
        bfn[i]=i;
    sort(bfn+1,bfn+1+n,cmp);
    for(int i=2;i<=n;i++)
        getdelf(i,i);
    for(int i=1;i<=q;i++){
        int x,y,res=0;
        read(x),read(y);
        for(int j=1;j<=n;j++)
            if(fa[j]!=1&&fa[j]!=x&&delp[x][fa[j]]&&delf[y][j])
                ok[j]=1;
        for(int j=2;j<=n;j++){
            ok[bfn[j]]|=ok[fa[bfn[j]]];
            res+=ok[bfn[j]];
        }
        for(int j=1;j<=n;j++)
            ok[j]=0;
        printf("%d\n",res);
    }
    return 0;
}

省选联考A卷全部题解可见：2021省选联考A卷解题报告