题解 P7516 [省选联考 2021 A/B 卷] 图函数

· · 题解

直接想没有思路的时候看怎么转化题意。 先手动模拟一次，发现当函数执行到 v=u 时，u 自己就被删掉了，所以 cnt 不会变化了。同时，到 v 的时候，1\sim v-1 都被删了，所以只能经过 \ge v 的点。所以翻译下 f(u) 就是图中满足 [u\leftrightarrow v](v),v\le u 的 v 的个数，其中定义 [u\leftrightarrow v] 表示 u,v 可以通过 \ge v 的点互达。（[u\leftrightarrow u]=1） 而所有时候我们需要的都是 \sum f(u)，因此 v\le u 的条件可以去掉，转为求 \sum f=\sum_{u,v} [u\leftrightarrow v](\min(u,v))。 先考虑第一问（图完整）。观察到 [] 为一种连通性关系，floyd 是用来求解此类问题的，再考虑如何解决所经点限制，floyd 有专门的一个循环来枚举所经点，当外层 k 从大到小枚举并在内层两个循环中加一些 if 就容易满足。 再考虑求出每个图，由于是边的有无影响了连通性，重要一点在于想到转化为（用 floyd）维护 一个点能到另一个点的最早时间，即最大的 i 使加入第 [i,m] 条边后一个点可以到达另一个点。

启示：

  1. 有关连通性的题目可以想 floyd
  2. 每次只改动一条边或类似情况，有时间轴思想、整体处理
  3. 图中类似于函数的叙述，力求破译其本质

轻微卡常即可写出代码。复杂度 O(n^3)。

#include <bits/stdc++.h>
using namespace std;
const int N=1005,M=2e5+5;
int n,m,f[N][N],ans[M];
inline int read(){
    register char ch=getchar();register int x=0;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
void print(int x){
    if(x/10)print(x/10);
    putchar(x%10+48);
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)f[i][i]=m+1;
    for(int i=1,u,v;i<=m;i++)u=read(),v=read(),f[u][v]=i;
    for(int k=n;k;k--){
        for(int i=1;i<=k;i++)
            for(int j=1;j<=n;j++){
                if(f[i][k]&&f[k][j])f[i][j]=max(f[i][j],min(f[i][k],f[k][j]));
            }
        for(int i=k+1;i<=n;i++)
            for(int j=1;j<=k;j++){
                if(f[i][k]&&f[k][j])f[i][j]=max(f[i][j],min(f[i][k],f[k][j]));
            }
    }
    for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)ans[min(f[i][j],f[j][i])]++;
    for(int i=m;i;i--)ans[i]+=ans[i+1];
    for(int i=1;i<=m+1;i++)print(ans[i]),putchar(' ');
}