[APIO2018] Duathlon 铁人两项

· · 题解

题目

  点这里看题目。

分析

  首先，我们很容易看出，在 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;
}