联合省选2021-Day1-T3

· · 题解

Solution

考虑 f(i,G) 的实际含义：

在 [1,i] 这段范围内的点 x（在 i 之后的点就一定没贡献了，因为 i 自己以及连出的边都删除了），我们用 g(i,x) 表示循环到它的时候它满足条件 i\to x 和 x\to i，也就是两点连通。

那么按照题意，按顺序考虑每个点的时候，若满足 [g(i,x)]，那么就会将这个点删去。

会注意到我们不需要真的执行删除这一操作，因为实际上 g(i,x) 等价于：同时存在路径 i \to x 和 x \to i 满足不经过点 [1,x)。

关于这里的等价转化，实际是需要分讨的，我们考虑一个点 y\in [1,x)：

第二种情况会有四种情况，手枚一下便会发现是矛盾的 case。

我们定义两个点 y,x(y<x) 贴贴 当且仅当当前的边集 G 使得 [g(i,x)] 成立。会注意到对于每个边集，我们要求的就是 贴贴 的点对数。特殊的，每个点一定和自己贴贴，和边集无关。

将时间轴倒过来，变成加边，那么随着边的增加，贴贴的对数不可能减少。于是我们只要可以求出每一对点 最早的贴贴时间，就可以通过一个差分来实现 \operatorname O(m) 求得所有答案。

回顾一下 g(y,x),y<x 的定义：从 x/y 出发，只经过 [y,n] 范围内的点，能够到达 y/x。

看到这个东西是不是非常熟悉？没错，这就是 Floyd。

只要从大到小枚举中间转移点，然后按正常的做法跑 Floyd，就可以得到前面提到的差分数组。

于是就有了优秀的 \operatorname O(n^3+m) 的做法。

考场 Code

除了把乱码注释删去以外，没做更改。

#include <stdio.h>
#define LL long long
using namespace std;
const int Rea=1e5+3;
struct Rin
{
    char c;
    inline char gc()
    {
        static char rea[Rea];
        static char *head,*tail;
        return head==tail&&(tail=(head=rea)+fread(rea,1,Rea,stdin),head==tail)?EOF:*head++;
    }
    inline Rin&operator >>(int &x)
    {
        x=0;
        bool tag=false;
        for(c=gc();c>'9'||c<'0';c=gc())if(c=='-'){c=gc();tag=true;break;}
        for(;c>='0'&&c<='9';c=gc())x=(x<<1)+(x<<3)+(c^'0');
        if(tag)x=-x;return *this;
    }
}rin;
inline void jh(int &x,int &y){if(x^y)x^=y^=x^=y;return;}
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}

const int N=1e3+3;
const int M=2e5+3;
int n,m;
int u[N];
int v[N];
int f[N][N];

int g[M];
int ans[M];
int main()
{
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    rin>>n>>m;for(int i=1;i<=m;i++)rin>>u[i]>>v[i],f[u[i]][v[i]]=i; 
    for(int k=n;k>=1;k--)
    {
        for(int i=k+1;i<=n;i++)g[min(f[k][i],f[i][k])]++;
        for(int i=1;i<=n;i++)
        {
            if(!f[i][k])continue;int nows=f[i][k];
            if(i>k)for(int j=1;j<k;j++)f[i][j]=max(f[i][j],min(nows,f[k][j]));
            else for(int j=1;j<=n;j++)f[i][j]=max(f[i][j],min(nows,f[k][j]));
        }
    }
    ans[m+1]=n;for(int i=m;i>=1;i--)ans[i]=ans[i+1]+g[i];
    for(int i=1;i<=m+1;i++)printf("%d ",ans[i]);puts("");
    return 0;
}