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

Aly_ · 2021-04-17 10:50:13 · 题解

一个究极暴力做法

题意简述

给定一张有向图 G，定义一个点 i 的支配集是所有满足如下性质的点：删除该点后 1 不再可达 i。
回答 q 个询问 <p_j,q_j>，询问的是加入边 p_j\rightarrow q_j 后多少个点的支配集发生变化。

解法

一步一步推。

以下是考场上的思考：

加入一条边后一个点的支配集要么变小，要么不变。因为这条边使整张图 “ 更加联通 ”。
支配的传递关系：若 x 支配 y，y 支配 z，则 x 支配 z。因为删除 x 后 y 被割开，而 y 一旦不可达 z 也就随之不可达了。
支配的链式关系：若 x 支配 a，y 也支配 a，则 x,y 之间也存在支配关系。如不然则必定有一种情况，使得删除其中一个点后，1 可从另一个点到达 a。
支配树：对于一个点 x，设 D_x 为它的支配集，则 D_x 中必定有且仅有一个点 fa_x，使得 D_x 中除 fa_x 的点都支配 y。这个性质可由上面的观察得出。我们新建一棵以 1 为根的树，其中包含所有 (x,fa_x) 无向边，此即为该无向图的支配树。
x 的支配集中，fa_x 是支配集大小最大的那个点。这点可由前面得出。通过这点可以暴力地构建支配树。
加入一条边后，x 的支配集发生改变时，要么 fa_x 的支配集发生改变，要么 fa_x 不再是 x 的支配点。这点可由上面支配树的定义看出。
加入一条边 p\rightarrow q 后，fa_x 不再是 x 的支配点，当且仅当删除 fa_x 后 1 可达 p，q 可达 x。可能有一些诸如 q=fa_x 的边角情况，特殊判掉即可。

于是出现了一个很暴力的做法。该做法分为 O(n^2) 的预处理和 O(nq) 的询问两部分。

依次遍历所有点，看看把它删掉后哪些点不再可达。这样可以求出每个点的支配集。由前面的第六点思考，我们得以构建支配树。构建完后，对于每个点 x，我们把它的父亲删掉，看看哪些点仍从 1 可达，哪些点仍可达 x。暴力 BFS，复杂度 O(n^2)。

查询时在树上 DFS。运用第七点和第八点综合判定即可。单次复杂度 O(n)。

总复杂度 O(n^2+nq)。空间 O(n^2)。可以通过本题。

下面是巨丑考场代码。有微调。

#include<bits/stdc++.h>
#define N 3005
using namespace std;
int n,m,Q,p,q,fa[N+1],fl[N+1][N+1],t[N+1],tfl[N+1][N+1],gfl[N+1];
vector<int>bi[N+1],fbi[N+1],o[N+1];
pair<int,int>q0[100001];
bool comp(int x,int y){return o[x].size()<o[y].size();}
void putin(){
    cin>>n>>m>>Q;
    for(int i=1;i<=m;i++)cin>>p>>q,bi[p].push_back(q),fbi[q].push_back(p);
    for(int i=1;i<=Q;i++)cin>>q0[i].first>>q0[i].second;
}
inline void dfs0(int x,int np){
    fl[x][np]=1;
    if(x==np)return;
    for(int i=0;i<bi[x].size();i++){
        int ni=bi[x][i];
        if(!fl[ni][np])dfs0(ni,np);
    }
}
void ycl(){
    dfs0(1,0);
    for(int i=1;i<=n;i++)t[i]=i;
    for(int i=1;i<=n;i++){
        dfs0(1,i);
        for(int j=1;j<=n;j++)if(fl[j][0]&&!fl[j][i])o[j].push_back(i);
    }
    sort(t+1,t+n+1,comp);
    for(int i=1;i<=n;i++){
        for(int j=0;j<o[i].size();j++){
            if(o[o[i][j]].size()==o[i].size()-1){
                fa[i]=o[i][j];break;
            }
        }
    }
}
inline void dfs1(int x,int np,int nr){
    if(x==nr)return;
    tfl[x][np]=1;
    for(int i=0;i<fbi[x].size();i++){
        int ni=fbi[x][i];
        if(!tfl[ni][np])dfs1(ni,np,nr);
    }
}
void cal0(){
    for(int i=2;i<=n;i++){
        dfs1(i,i,fa[i]);
    }
    for(int i=1;i<=Q;i++){
        int nans=0;
        for(int j=1;j<=n;j++)if(fl[q0[i].first][fa[j]]&&tfl[q0[i].second][j]&&fa[j]!=1&&fa[j]!=q0[i].first)gfl[j]=1;
        for(int j=1;j<=n;j++)if(gfl[fa[t[j]]])gfl[t[j]]=1;
        for(int j=1;j<=n;j++)if(gfl[j])nans++,gfl[j]=0;
        cout<<nans<<'\n';
    }
}
signed main(){
    putin();
    ycl();
    cal0();
    return 0;
}

~~省选救命题~~

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

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