网站主页设计欣赏,自建网站的劣势,金华网站建设明细报价表,优秀seo外包平台正题
题目链接:https://www.luogu.com.cn/problem/P7520 题目大意
给出nnn个点mmm条边的一张有向图#xff0c;一号点为起始点#xff0c;qqq次独立的询问加入一条边后有多少个点的支配集发生了变化。 1≤n≤3000,1≤m≤2n,1≤q≤21041\leq n\leq 3000,1\leq m\leq 2\times…正题
题目链接:https://www.luogu.com.cn/problem/P7520 题目大意
给出nnn个点mmm条边的一张有向图一号点为起始点qqq次独立的询问加入一条边后有多少个点的支配集发生了变化。
1≤n≤3000,1≤m≤2×n,1≤q≤2×1041\leq n\leq 3000,1\leq m\leq 2\times n,1\leq q\leq 2\times 10^41≤n≤3000,1≤m≤2×n,1≤q≤2×104 解题思路
首先我们肯定是先建一棵支配树可以直接O(n2)O(n^2)O(n2)搞。
具体的做法我是从1∼n1\sim n1∼n枚举然后枚举到xxx时把xxx删掉从111开始遍历如果对于一个点yyy满足yyy不能到达且fayfa_yfay能够到达那么fayfa_yfay改为xxx即可。
然后考虑一条边x→yx\rightarrow yx→y能改变支配集的话防止麻烦我们对于每个点xxx只考虑它的父节点faxfa_xfax如果1∼y1\sim y1∼y存在一个点xxx使得faxfa_xfax不再支配xxx那么yyy的支配集肯定改变。
那么考虑对于一个边x→yx\rightarrow yx→y如果存在一条路径1→x→y→i1\rightarrow x\rightarrow y\rightarrow i1→x→y→i且不经过iii的父节点那么iii整个子树的支配集都会改变首先条件是1→x1\rightarrow x1→x不经过faifa_ifai这个很简单如果xxx不在faifa_ifai的子树内就好了。然后是y→iy\rightarrow iy→i这个条件也很好搞枚举点iii把faifa_ifai删去然后看iii走反图能到达的点这些点都可以作为yyy提前O(n2)O(n^2)O(n2)预处理就好了。
然后询问的时候我们暴力枚举所有点判断是否合法然后树上差分来统计答案就好了。
时间复杂度O(n2nq)O(n^2nq)O(n2nq) code
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N3010;
int n,m,q,cnt,ans,fa[N],v[N],rfn[N],ed[N];
vectorint F[N],G[N],T[N];
bool f[N][N];
void dfs(int x){if(v[x])return;v[x]1;for(int i0;iG[x].size();i)dfs(G[x][i]);return;
}
void dfs2(int x){rfn[x]cnt;for(int i0;iT[x].size();i)dfs2(T[x][i]);ed[x]cnt;return;
}
void dfs3(int x){if(v[x])return;v[x]1;for(int i0;iF[x].size();i)dfs3(F[x][i]);return;
}
void dfs4(int x,int w){w|v[x];answ;for(int i0;iT[x].size();i)dfs4(T[x][i],w);return;
}
int main()
{scanf(%d%d%d,n,m,q);for(int i1,x,y;im;i){scanf(%d%d,x,y);G[x].push_back(y);F[y].push_back(x);}for(int i1;in;i){memset(v,0,sizeof(v));v[i]2;dfs(1);v[0]1;for(int j1;jn;j)if(!v[j]v[fa[j]])fa[j]i;}for(int i2;in;i)T[fa[i]].push_back(i);dfs2(1);for(int i2;in;i){memset(v,0,sizeof(v));v[fa[i]]2;dfs3(i);for(int j1;jn;j)if(v[j]1)f[j][i]1;}while(q--){int x,y;ans0;memset(v,0,sizeof(v));scanf(%d%d,x,y);for(int i1;in;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;
}
