自动搬运

查看原文

来自洛谷，原作者为

	zjjws Dirty Deeds Done Dirt Cheap

搬运于2025-08-24 22:30:36，当前版本为作者最后更新于2021-04-10 14:12:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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)$：

• $y$ 做了贡献，使 $cut+1$ 并且被删除。那么此时显然成立。

• $y$ 没做贡献，那么此时 $i,y$ 之间至少有一条某方向的路径不连通。如果 $x\to i$ 或者 $i\to x$ 的某一条路径一定要经过 $y$ 点，那么就出现了一个矛盾的情况：$y,i$ 有且仅一个方向的通路，$x,i$ 可互相到达，并且其中一条通路中，$y$ 是必经点。

第二种情况会有四种情况，手枚一下便会发现是矛盾的 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;
}