正题

题目链接:https://www.luogu.com.cn/problem/P7516

---

题目大意

懒了，直接抄题意了
对于一张 $n$ 个点 $m$ 条边的有向图 $G$（顶点从 $1\sim n$ 编号），定义函数 $f(u,G)$：

初始化返回值 $cnt=0$，图 $G^{\prime }=G$。

从 $1$ 至 $n$ 按顺序枚举顶点 $v$，如果当前的图 $G^{\prime };$ 中，从 $u$ 到 $v$ 与从 $v$ 到 $u$ 的路径都存在，则将 $cnt+1$，并在图 $G^{\prime };$ 中删去顶点 $v$ 以及与它相关的边。

第 $2$ 步结束后，返回值 $cnt$ 即为函数值。

现在给定一张有向图 $G$，请你求出 $h(G)=f(1,G)+f(2,G)+\cdots +f(n,G)$ 的值。

更进一步地，记删除（按输入顺序给出的）第 $1$ 到 $i$ 条边后的图为 $G_i$（$1\le i\le m$），请你求出所有 $h(G_i)$ 的值。

$1\le n\le 10^3,1\le m\le 2\times 10^5$

---

解题思路

但凡一个不按惯性思维思考的方法都可以做出这道题

这个删边就很意义不明，反过来直接改成加边就简单很多。

然后还有一个问题就是是否删点的判断也是没有必要的：

假设对于起点$u$能走到$v$，$v$不能走到$u$，那么显然并不存在一个节点$x$使得$u$能走到$x$且$x$能走到$u$并且$v$是这些路径的必经点，因为那么$v$肯定在这个环上，那么$v$显然能走到$u$。

所以现在$f(u,G)$能否统计$v$就变为了判断是否存在一个$u\to v\to u$的环使得路径上的所有点编号不小于$min(u,v)$。

那么不妨考虑一下两个点对$(u,v)$之间不断加边之后第一次产生贡献的时间，每条边的权值设为加入的时间，这个时间就是$u\to v\to u$的一条不经过编号小于$min(u,v)$点的情况下最大权值最小的路径。

这样Flody就有$O(n^3)$的算法了。

然后我们想了很久感觉最短路行不通，那么此时就需要摒弃惯性思维的想法了，我们考虑另一个更暴力的做法，我们每次加边然后暴力判断每个点之间的联通，发现这样的时间复杂度是$O(n{m}^2)$的。

然后依旧的我们考虑另一种可能，我们最外层不枚举加边，而是枚举需要统计答案的起点$u$，然后每次加一条边$(x,y)$，如果$u$能走到$x$且不能走到$y$那么此时$u$能走到$y$了，从$y$开始$bfs$所有其他没有走过的节点，需要注意的是走过的边两边都是遍历过的所以可以直接删除。

这样的时间复杂度就是$O(n(n+m))$，可以通过本题。

需要卡常

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; const int N=1e3+10,M=2e5+10; struct node{int to,next; }a[M]; int n,m,f[N][N],g[N][N]; int ex[M],ey[M],ans[M]; vector<int> G[N],D[N];queue<int> q; void bfs(int x,int s,int w){q.push(x);while(!q.empty()){int x=q.front();q.pop();f[s][x]=w;for(int i=0;i<G[x].size();i++)if(!f[s][G[x][i]])q.push(G[x][i]);G[x].clear();}return; } void bgs(int x,int s,int w){q.push(x);while(!q.empty()){int x=q.front();q.pop();g[s][x]=w;for(int i=0;i<D[x].size();i++)if(!g[s][D[x][i]])q.push(D[x][i]);D[x].clear();}return; } int main() {scanf("%d%d",&n,&m);m++;for(int i=2;i<=m;i++)scanf("%d%d",&ex[i],&ey[i]);reverse(ex+2,ex+1+m);reverse(ey+2,ey+1+m);for(int x=1;x<=n;x++){for(int i=1;i<=n;i++)G[i].clear();for(int i=1;i<=n;i++)D[i].clear();f[x][x]=g[x][x]=1;for(int i=2;i<=m;i++){if(ex[i]<x||ey[i]<x)continue;if(f[x][ex[i]]&&!f[x][ey[i]])bfs(ey[i],x,i);else if(!f[x][ex[i]]&&!f[x][ey[i]])G[ex[i]].push_back(ey[i]);if(g[x][ey[i]]&&!g[x][ex[i]])bgs(ex[i],x,i);else if(!g[x][ey[i]]&&!g[x][ex[i]])D[ey[i]].push_back(ex[i]);}}for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)if(f[i][j]&&g[i][j])ans[max(f[i][j],g[i][j])]++;for(int i=1;i<=m;i++)ans[i]+=ans[i-1];reverse(ans+1,ans+1+m);for(int i=1;i<=m;i++)printf("%d ",ans[i]);return 0; }

总结

以上是生活随笔为你收集整理的P7516-[省选联考2021A/B卷]图函数【bfs】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。