自动搬运

查看原文

来自洛谷，原作者为

	crashed 让我们登上这座山！

搬运于2025-08-24 22:02:07，当前版本为作者最后更新于2020-07-23 09:18:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目

  点这里看题目。

分析

  首先，我们很容易看出，在 $s$ 和 $f$ 确定时，$c$ 的备选数量就等于从$s$到$f$所有简单路径的并的大小减二 （要把$s$和$f$去掉）。
  随手画几个图就会发现， $s$ 到 $f$ 所有简单路径的并似乎也就是从$s$到$f$经过的所有点双的并。
  考虑证明这个猜想。首先，由于点双之间最多只有一个公共点，所以每个点双内，每条从 $s$ 到 $f$ 的简单路径，必然是从一个固定点进入点双，从另一个固定点离开。
  因而我们只需要再证明：在点双内部，对于任意三点$a, b, c$，必然存在简单路径满足从$a$到$c$到$b$。
  为了方便，以下用$u\overset{c}{\rightarrow}v$表示从$u$向$v$连一条容量为$c$的边。
  考虑构建一个网络来证明，如下：
  1. 拆点。对于$u$拆成$u$和$u'$，并且连接$u\overset{1}{\rightarrow} u'$，表示每个点只能经过一次。
  2. 拆边。无向边先要拆成有向边。对于有向边$(u,v)$，连接$u'\overset{1}{\rightarrow} v$，表示边只能经过一次。
  3. 连接源汇。连接$S\overset{2}{\rightarrow} c, a'\overset{1}{\rightarrow} T,b'\overset{1}{\rightarrow} T$。
  这样，如果原图最大流为 $2$ ，则存在需要的路径。
  也就是说，我们需要证明，原图最大流，也即是最小割为 $2$ 。
  设最小割为$C$。显然$C\le 2$。那么我们需要证明$C>1$，即不可以只删除一条边就使得$S$到$T$不连通。
  分类讨论：
  1. 如果删除 $u\overset{1}{\rightarrow} u'$ 的边，我们就相当于拆掉了一个点。根据点双的定义，不影响连通性。
  2. 如果删除 $u'\overset{1}{\rightarrow} v$ 的边，我们就相当于拆掉了一条边。由于这个操作影响比拆点更小，因而也不影响连通性。
  3. 删除$a'\overset{1}{\rightarrow} T$或者是$b'\overset{1}{\rightarrow} T$。显然只删除一边而另一边留存都不会影响连通性。
  因而有$C>1$，根据连边特性我们知道就有$C=2$，即命题成立。
  这也就是说，我们的猜想也是成立的。

  因而我们只需要统计任意两点之间，经过的点双的并的大小减二即可。
  考虑建出圆方树，这样任意两点之间经过的点双就是路径上的方点。
  下面需要使用到一个技巧：为圆方树上的点赋合适的权。
  这一题中，我们首先可以猜想给方点赋为点双大小。由于两个点双之间最多只有一个交点，因而我们可以直接给圆点赋为 $-1$ 进行扣除多余贡献。同时，圆点赋 $-1$ 也能顺带处理 " 并集大小减二 " 这个情况。
  总结一下，我们给圆点赋 $-1$ ，方点赋大小，然后统计任意两个圆点之间路径的权值和即可。建出圆方树后一边 DFS 计算答案即可。时间$O(n)$。

代码

#include <cstdio>

typedef long long LL;

const int MAXN = 2e5 + 5, MAXM = 2e6 + 5;

template<typename _T>
void read( _T &x )
{
	x = 0;char s = getchar();int f = 1;
	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
	x *= f;
}

template<typename _T>
void write( _T x )
{
	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
	if( 9 < x ){ write( x / 10 ); }
	putchar( x % 10 + '0' );
}

template<typename _T>
_T MIN( const _T a, const _T b )
{
	return a < b ? a : b;
}

struct GRAPH
{
	struct edge
	{
		int to, nxt;
	}Graph[MAXM << 1];
	
	int head[MAXN] = {}, cnt;
	
	GRAPH() { cnt = 0; }
	
	void addEdge( const int from, const int to )
	{
		Graph[++ cnt].to = to, Graph[cnt].nxt = head[from];
		head[from] = cnt;
	}
	
	void addE( const int from, const int to )
	{
		addEdge( from, to ), addEdge( to, from );
	}
	
	void nxt( int &ptr ) const { ptr = Graph[ptr].nxt; }
	edge& operator [] ( const int indx ) { return Graph[indx]; }
}G, T;

int stk[MAXN];
int siz[MAXN], w[MAXN];
int DFN[MAXN], LOW[MAXN];
LL ans;
int N, M, cnt, ID, top, tot, subn;

void Tarjan( const int u, const int fa )
{
	subn ++;
	DFN[u] = LOW[u] = ++ ID;
	w[stk[++ top] = u] = -1;
	for( int i = G.head[u], v ; i ; G.nxt( i ) )
		if( ( v = G[i].to ) ^ fa )
		{
			if( ! DFN[v] )
			{
				Tarjan( v, u );
				LOW[u] = MIN( LOW[u], LOW[v] );
				if( LOW[v] >= DFN[u] )
				{
					T.addE( ++ tot, u ), w[tot] ++;
					do T.addE( tot, stk[top] ), w[tot] ++;
					while( stk[top --] ^ v );
				}
			}
			else LOW[u] = MIN( LOW[u], DFN[v] );
		}
}

void DFS( const int u, const int fa )
{
	siz[u] = u <= N;
	for( int i = T.head[u], v ; i ; T.nxt( i ) )
		if( ( v = T[i].to ) ^ fa )
		{
			DFS( v, u ); 
			ans += 2ll * siz[u] * siz[v] * w[u];
			siz[u] += siz[v];
		}
	ans += 2ll * siz[u] * ( subn - siz[u] ) * w[u];
}

int main()
{
	read( N ), read( M ), tot = N;
	for( int i = 1, a, b ; i <= M ; i ++ )
		read( a ), read( b ), G.addE( a, b );
	for( int i = 1 ; i <= N ; i ++ )
		if( ! DFN[i] )
		{
			subn = 0;
			Tarjan( i, 0 );
			DFS( i, 0 );
		}
	write( ans ), putchar( '\n' );
	return 0;
}