洛谷题单指南-树与图上的动态规划-P7516 [省选联考 2021 A/B 卷] 图函数

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

题意解读：本题仍未吃透，请酌情参考。

（参考洛谷题解https://www.luogu.com.cn/article/gr0lbeol）

当函数执行到 v=u 时，u 自己就被删掉了，所以 cnt 不会变化了。

同时，到 v 的时候，1∼v−1 都被删了，所以只能经过 ≥v 的点。

所以 f(u) 就是图中满足 u↔v,v≤u 的 v 的个数，其中定义 [u↔v] 表示 u,v 可以通过 ≥v 的点互达。（[u↔u]=1）而所有时候我们需要的都是 ∑f(u)，因此 v≤u 的条件可以去掉，转为求 ∑f=∑u,vu↔v)。

先考虑第一问（图完整）。观察到 [] 为一种连通性关系，floyd 是用来求解此类问题的，再考虑如何解决所经点限制，floyd 有专门的一个循环来枚举所经点，当外层 k 从大到小枚举并在内层两个循环中加一些 if 就容易满足。再考虑求出每个图，由于是边的有无影响了连通性，重要一点在于想到转化为（用 floyd）维护一个点能到另一个点的最早时间，即最大的 i 使加入第 [i,m] 条边后一个点可以到达另一个点。

解题思路：

设f[i][j]表示i、j互通的最早时间，由于是逆着时间加边，就是最大的时间值，时间就是边的序号。

初始化：for(int i=1;i<=n;i++)f[i][i]=m+1

对于每条边：f[u][v]=i;

转移方程：f[i][j]=max(f[i][j],min(f[i][k],f[k][j]))，约束为当i>k是，j<=k；i<=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];

80分代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 200005;
int f[N][N], ans[M];
int n, m;

int main(){
    cin >> n >> m;
    for(int i=1; i<=n; i++) f[i][i] = m + 1;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        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++) cout << ans[i]<< " ";
    return 0;
}