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

解题报告

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

更好的阅读体验

题意

给定一张$n$个点$m$条边的有向图$G$，定义函数$f(u,G)$的值为下列操作的返回值：

设$cnt=0,G'=G$，然后按$1$到$n$的顺序枚举点$v$，如果$G'$中$v$与$u$能双向到达，那么$cnt++$，并删去结点$v$，最后返回$cnt$。

定义$h(G)=\sum_{i=1}^n f(i,G)$，并定义$G_i$为图$G$删除边$1\cdots i$后的图，求出$h(G_{0\cdots n})$。

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

分析

定义$g_{x,y}(x\leqslant y)$为$x$经过$[x,n]$的点能否到达$y$，同样设$g_{x,y}(x>y)$为$x$经过$[y,n]$的点能否到达$y$，那么对于图$G$，求的其实就是$\sum_{i\ne j}g_{i,j}\text{&}g_{j,i}$。

发现如果图改变需要重新处理值，这肯定会超时，因此将$g_{x,y}$中是否能到达改为删除最多的边使得能让其到达的边数（无法到达则为$0$）。

那么如果我们处理出$g_{x,y}$，我们可以求出答案的差分数组，然后前缀和就好了。

考虑类似Floyd的做法，从大到小枚举中转点$k$（这样做可以让循环到$k$时经过的点全部大于等于$k$，便于统计答案），然后对路径进行合并。

具体地，我们对于$\leqslant k$且可以经过$>k$的结点到达$k$（其实就是判断当时的$g_{i,k}$是否非零）的点$i$，枚举终点$j$，那么会存在一条$i\rightarrow k\rightarrow j$的路径，且不难发现这条路径删除的边数为$\min\{g_{i,k},g_{k,j}\}$，用这个权值更新$g_{i,j}$就好了。

同理对于$>k$且可以经过$>k$的结点到达$k$的点$i$，枚举终点$j$（这里的$j$要小于$k$，否则答案会算重。但其实算重也没关系，因为这一部分的答案已经在之前更新过了），按上面同样的方式更新答案就好了。

时间复杂度：$O(n^3+m)$。

代码

#include<stdio.h>
const int maxn=1005,maxm=200005;
int n,m;
int g[maxn][maxn],sum[maxm],ans[maxm];
inline int min(int a,int b){
    return a<b? a:b;
}
inline int max(int a,int b){
    return a>b? a:b;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        g[i][i]=m+1;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x][y]=i;
    }
    for(int k=n;k>=1;k--){
        for(int i=k;i<=n;i++)
            sum[min(g[i][k],g[k][i])]++;
        for(int i=1;i<=k;i++)
            if(g[i][k])
                for(int j=1;j<=n;j++)
                    g[i][j]=max(g[i][j],min(g[i][k],g[k][j]));
        for(int i=k+1;i<=n;i++)
            if(g[i][k])
                for(int j=1;j<k;j++)
                    g[i][j]=max(g[i][j],min(g[i][k],g[k][j]));
    }
    for(int i=m;i>=1;i--)
        sum[i]+=sum[i+1];
    for(int i=1;i<=m+1;i++)
        printf("%d%c",sum[i],i==m+1? '\n':' ');
    return 0;
}

省选联考A卷全部题解可见：2021省选联考A卷解题报告