正题
题目链接:https://www.luogu.com.cn/problem/P7516
题目大意
懒了，直接抄题意了
对于一张 \(n\) 个点 \(m\) 条边的有向图 \(G\)（顶点从 \(1 \sim n\) 编号），定义函数 \(f(u, G)\)：
- 初始化返回值 \(cnt = 0\)，图 \(G'= G\)。
- 从 \(1\) 至 \(n\) 按顺序枚举顶点 \(v\)，如果当前的图 \(G';\) 中，从 \(u\) 到 \(v\) 与从 \(v\) 到 \(u\) 的路径都存在，则将 \(cnt + 1\)，并在图 \(G';\) 中删去顶点 \(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\leq n\leq 10^3,1\leq m\leq 2\times 10^5\)
解题思路
但凡一个不按惯性思维思考的方法都可以做出这道题
这个删边就很意义不明，反过来直接改成加边就简单很多。
然后还有一个问题就是是否删点的判断也是没有必要的：
假设对于起点\(u\)能走到\(v\)，\(v\)不能走到\(u\)，那么显然并不存在一个节点\(x\)使得\(u\)能走到\(x\)且\(x\)能走到\(u\)并且\(v\)是这些路径的必经点，因为那么\(v\)肯定在这个环上，那么\(v\)显然能走到\(u\)。
所以现在\(f(u,G)\)能否统计\(v\)就变为了判断是否存在一个\(u\rightarrow v\rightarrow u\)的环使得路径上的所有点编号不小于\(min(u,v)\)。
那么不妨考虑一下两个点对\((u,v)\)之间不断加边之后第一次产生贡献的时间，每条边的权值设为加入的时间，这个时间就是\(u\rightarrow v\rightarrow u\)的一条不经过编号小于\(min(u,v)\)点的情况下最大权值最小的路径。
这样Flody就有\(O(n^3)\)的算法了。
然后我们想了很久感觉最短路行不通，那么此时就需要摒弃惯性思维的想法了，我们考虑另一个更暴力的做法，我们每次加边然后暴力判断每个点之间的联通，发现这样的时间复杂度是\(O(nm^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;
}