Aly_

一个究极暴力做法

题意简述

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

解法

​ 一步一步推。

​ 以下是考场上的思考：

1. 加入一条边后一个点的支配集要么变小，要么不变。因为这条边使整张图 “ 更加联通 ”。
2. 支配的传递关系：若 $x$ 支配 $y$，$y$ 支配 $z$，则 $x$ 支配 $z$。因为删除 $x$ 后 $y$ 被割开，而 $y$ 一旦不可达 $z$ 也就随之不可达了。
3. 支配的链式关系：若 $x$ 支配 $a$，$y$ 也支配 $a$，则 $x,y$ 之间也存在支配关系。如不然则必定有一种情况，使得删除其中一个点后，$1$ 可从另一个点到达 $a$。
4. 支配树：对于一个点 $x$，设 $D_x$ 为它的支配集，**则 $D_x$ 中必定有且仅有一个点 $fa_x$，使得 $D_x$ 中除 $fa_x$ 的点都支配 $y$。**这个性质可由上面的观察得出。我们新建一棵以 $1$ 为根的树，其中包含所有 $(x,fa_x)$ 无向边，此即为该无向图的支配树。
5. $x$ 的支配集为支配树上所有 $x$ 的祖先。
6. $x$ 的支配集中，$fa_x$ 是支配集大小最大的那个点。这点可由前面得出。通过这点可以暴力地构建支配树。
7. 加入一条边后，$x$ 的支配集发生改变时，要么 $fa_x$ 的支配集发生改变，要么 $fa_x$ 不再是 $x$ 的支配点。这点可由上面支配树的定义看出。
8. 加入一条边 $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;
}

省选救命题