题解 P7520【[省选联考 2021 A 卷] 支配】
whiteqwq
·
·
题解
P7520 [省选联考 2021 A 卷] 支配
更好的阅读体验
题意
定义一个点x支配另一个点y当且仅当结点1到达结点y的每一条路径都要经过x，且点y的受支配集D_y为所有支配y的x形成的集合。
给定一个n个点m条边的图G，进行q次相互独立的询问，每次询问加入边(x,y)后有多少个点的受支配集有变化。
## 分析
似乎是支配树裸题，但我不会支配树/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卷解题报告](https://zybuluo.com/xiaoziyao/note/1791034)