正題

題目鏈接:https://www.luogu.com.cn/problem/P7520

---

題目大意

給出$n$個(gè)點(diǎn)$m$條邊的一張有向圖，一號(hào)點(diǎn)為起始點(diǎn)，$q$次獨(dú)立的詢問加入一條邊后有多少個(gè)點(diǎn)的支配集發(fā)生了變化。

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

---

解題思路

首先我們肯定是先建一棵支配樹，可以直接$O(n^2)$搞。

具體的做法我是從$1～n$枚舉，然后枚舉到$x$時(shí)把$x$刪掉從$1$開始遍歷，如果對(duì)于一個(gè)點(diǎn)$y$滿足$y$不能到達(dá)且$f{a}_y$能夠到達(dá)，那么$f{a}_y$改為$x$即可。

然后考慮一條邊$x\to y$能改變支配集的話，防止麻煩我們對(duì)于每個(gè)點(diǎn)$x$只考慮它的父節(jié)點(diǎn)$f{a}_x$，如果$1～y$存在一個(gè)點(diǎn)$x$使得$f{a}_x$不再支配$x$，那么$y$的支配集肯定改變。

那么考慮對(duì)于一個(gè)邊$x\to y$，如果存在一條路徑$1\to x\to y\to i$且不經(jīng)過$i$的父節(jié)點(diǎn)，那么$i$整個(gè)子樹的支配集都會(huì)改變，首先條件是$1\to x$不經(jīng)過$f{a}_i$，這個(gè)很簡單，如果$x$不在$f{a}_i$的子樹內(nèi)就好了。然后是$y\to i$這個(gè)條件，也很好搞，枚舉點(diǎn)$i$，把$f{a}_i$刪去，然后看$i$走反圖能到達(dá)的點(diǎn)，這些點(diǎn)都可以作為$y$，提前$O(n^2)$預(yù)處理就好了。

然后詢問的時(shí)候我們暴力枚舉所有點(diǎn)判斷是否合法，然后樹上差分來統(tǒng)計(jì)答案就好了。

時(shí)間復(fù)雜度：$O(n^2+nq)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int N=3010; int n,m,q,cnt,ans,fa[N],v[N],rfn[N],ed[N]; vector<int> F[N],G[N],T[N]; bool f[N][N]; void dfs(int x){if(v[x])return;v[x]=1;for(int i=0;i<G[x].size();i++)dfs(G[x][i]);return; } void dfs2(int x){rfn[x]=++cnt;for(int i=0;i<T[x].size();i++)dfs2(T[x][i]);ed[x]=cnt;return; } void dfs3(int x){if(v[x])return;v[x]=1;for(int i=0;i<F[x].size();i++)dfs3(F[x][i]);return; } void dfs4(int x,int w){w|=v[x];ans+=w;for(int i=0;i<T[x].size();i++)dfs4(T[x][i],w);return; } int main() {scanf("%d%d%d",&n,&m,&q);for(int i=1,x,y;i<=m;i++){scanf("%d%d",&x,&y);G[x].push_back(y);F[y].push_back(x);}for(int i=1;i<=n;i++){memset(v,0,sizeof(v));v[i]=2;dfs(1);v[0]=1;for(int j=1;j<=n;j++)if(!v[j]&&v[fa[j]])fa[j]=i;}for(int i=2;i<=n;i++)T[fa[i]].push_back(i);dfs2(1);for(int i=2;i<=n;i++){memset(v,0,sizeof(v));v[fa[i]]=2;dfs3(i);for(int j=1;j<=n;j++)if(v[j]==1)f[j][i]=1;}while(q--){int x,y;ans=0;memset(v,0,sizeof(v));scanf("%d%d",&x,&y);for(int i=1;i<=n;i++){if(!f[y][i])continue;if(rfn[fa[i]]<=rfn[x]&&ed[fa[i]]>=rfn[x])continue;v[i]=1;}dfs4(1,0);printf("%d\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P7520-[省选联考 2021 A 卷]支配的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。