题解 P7516【[省选联考 2021 A/B 卷] 图函数】
whiteqwq
·
·
题解
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})。
## 分析
定义$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{and}\ 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卷解题报告](https://zybuluo.com/xiaoziyao/note/1791034)