最大流

GitHub跳转原题关系图返回列表

度数不超过 3 时点对最大流只可能是 0/1/2/3,用并查集、边双连通分量与「删每条边后的边双划分」三层等价类分别数出流量至少 1/2/3 的点对数。

OJ: roj

题目 ID: 1731

难度:提高+/省选-

标签:图论边双连通分量最大流最小割并查集python

创建: 2026-10-07 20:29

更新: 2026-10-07 20:29

形式化题目

给定一张 nn 个点、mm 条边的无向图,点从 11 开始编号,保证所有点的度数都不超过 33, 无重边无自环。把每条边的容量都看成 11,设 f(i,j)f(i,j) 是 ii 到 jj 的最大流,求

∑1⩽i<j⩽nf(i,j).\sum_{1 \leqslant i < j \leqslant n} f(i,j).

数据范围:2⩽n⩽30002 \leqslant n \leqslant 3000,0⩽m⩽⌊3n2⌋0 \leqslant m \leqslant \left\lfloor \dfrac{3n}{2} \right\rfloor。 输出一行一个整数。

样例 1:n=4n = 4、两条边 (1,2),(3,4)(1,2),(3,4),答案是 22(只有这两对点连通,各贡献 11)。 样例 2:n=6n = 6、m=8m = 8,答案是 3636。

正解

思路

朴素做法的规模。 直接对每一对点跑一次最大流:点对数是 O(n2)≈4.5×106O(n^2) \approx 4.5 \times 10^6, 每次跑 Dinic 是 O(mm)O(m\sqrt{m}) 量级,总代价约 101110^{11},无论怎么优化都不可能过。 但正因为点数 nn 到 30003000 而度数只有 33,答案的取值范围极端狭窄——这是全部突破口。

关键观察一:流量只可能是 0,1,2,30,1,2,3。 由最大流最小割定理,任何 i→ji \to j 的流量都不超过 "只割 ii 的关联边"这一个割的大小,即不超过 deg⁡(i)\deg(i);同理也不超过 deg⁡(j)\deg(j)。于是

f(i,j)⩽min⁡{deg⁡(i),deg⁡(j)}⩽3.f(i,j) \leqslant \min\{\deg(i), \deg(j)\} \leqslant 3 .

所以 f(i,j)∈{0,1,2,3}f(i,j) \in \{0,1,2,3\},而

∑i<jf(i,j)=∑k=13#{(i<j):f(i,j)⩾k}=cnt1+cnt2+cnt3.\sum_{i<j} f(i,j) = \sum_{k=1}^{3} \#\{(i<j) : f(i,j) \geqslant k\} = \mathrm{cnt}_1 + \mathrm{cnt}_2 + \mathrm{cnt}_3 .

问题从"求每对点的流量"变成了"对 k=1,2,3k = 1,2,3 各数一次点对",每层都退化成图的结构判定。

关键观察二:三层判定分别对应三种连通性。

  • f(i,j)⩾1f(i,j) \geqslant 1:等价于 i,ji,j 在原图中连通。⇐\Leftarrow 沿任一条路径推 11 单位流; ⇒\Rightarrow 不连通则割集为空、流量 00。→ 用并查集数连通分量内的点对数。
  • f(i,j)⩾2f(i,j) \geqslant 2:等价于 i,ji,j 属于同一边双连通分量(22-边连通)。 两条边不相交路径正是 22-边连通的定义(Menger 定理);反过来若存在桥把两点分开, 割集只有那一条边,流量至多 11。→ 求出所有桥,忽略桥做 flood-fill,数同一块内的点对数。
  • f(i,j)⩾3f(i,j) \geqslant 3:等价于删掉任意一条边后 i,ji,j 仍在该图的同一边双连通分量里。 一方面 33 条边不相交路径删掉一条还剩 22 条;另一方面只要某条边 ee 一删就把 i,ji,j 分开, 则 ee 与另一条分开 i,ji,j 的割边构成大小 22 的割,流量至多 22。这就是本层的判据。

前两层各扫一遍图即可,第三层看起来需要"对每条边删一次再求边双",也就是 O(m)O(m) 次 O(n+m)O(n+m) 的 Tarjan,总代价 O(m(n+m))=4500×7500≈3.4×107O(m(n+m)) = 4500 \times 7500 \approx 3.4 \times 10^7, 在 3 s 的限时下完全够用。剩下的只是"如何数点对数"和"如何比较两轮划分"这两个工程问题。

第三层怎么落地:等价类精化。 设 bele(v)\mathrm{bel}_e(v) 是删掉边 ee 后 vv 所属的边双分量号。 条件"对每条边 ee 都有 bele(i)=bele(j)\mathrm{bel}_e(i) = \mathrm{bel}_e(j)"不能直接对 mm 个整数数组逐对比较, 但可以把它写成一串逐步细化的划分:

cls0(v)≡0,clsk(v)=把 (clsk−1(v), belek(v)) 重新编号,\mathrm{cls}_0(v) \equiv 0, \qquad \mathrm{cls}_{k}(v) = \text{把 } \big(\mathrm{cls}_{k-1}(v),\, \mathrm{bel}_{e_k}(v)\big) \text{ 重新编号},

其中把二元组按字典序排序后重编号,编号相同当且仅当二元组相同。 这样的"精化"只有分裂没有合并,mm 轮之后 clsm(i)=clsm(j)\mathrm{cls}_m(i) = \mathrm{cls}_m(j) 恰好等价于"每一轮都在同一分量里",也就是 f(i,j)⩾3f(i,j) \geqslant 3,最后数一次同一类内的点对数即可。

几个可以省掉的工作量:

  • 桥不必检验。 删掉一条桥只会让划分变细(桥本来就不在任何非平凡边双块内), 不会把原本同块的边双划分拆开,所以只对满足 bel−1(u)=bel−1(v)\mathrm{bel}_{-1}(u) = \mathrm{bel}_{-1}(v) 的非桥边跑循环。
  • 类数达到 nn 就收工。 全是单点时再细分也只能保持单点,此时每个类只有 11 个点、 点对数为 00,可以直接 break。
  • 重编号用确定性手段,不用哈希。 Python 版把二元组压成 cls[v]*(n+1)+bel[v] 当作 dict 的键(键互不相同,不存在冲突);C++ 版更进一步,用两趟计数排序 (先按 bel 稳定排序、再按 cls 稳定排序)把每轮压到 O(n)O(n),连排序的 log⁡\log 因子和哈希表开销都省了。两边的划分结果完全一致。

一个容易踩的边界: m=0m = 0 时没有任何"删一条边"的检验,cnt3=0\mathrm{cnt}_3 = 0, 答案就是 cnt1+cnt2\mathrm{cnt}_1 + \mathrm{cnt}_2(样例 1 正是这种情况:n=4,m=2n = 4, m = 2 时 cnt1=2\mathrm{cnt}_1 = 2、cnt2=0\mathrm{cnt}_2 = 0、cnt3=0\mathrm{cnt}_3 = 0,答案 22)。 另外 Tarjan 要求图可能不连通,必须对每个未访问的点各起一次 DFS。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 20:29
# update_at: 2026-10-07 20:29

import sys

NO_BAN = -1  # 求「原图」时的 ban 取值:一条边都不删
ALL_EDGES = None  # 传给 flood 的 skip 参数:没有任何边被标成桥(全部边都保留)

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Csr = tuple[list[int], list[int], list[int], list[int]]  # CSR:区间起点 / 邻点 / 邻边号 / 度数
type EdgeList = list[tuple[int, int]]                         # 原始边表,下标就是边编号
type ClassCount = dict[int, int]                              # 等价类号 -> 该类里的点数
type ClassRank = dict[int, int]                               # (上一轮类号, 本轮分量号) 编成的复合键 -> 新类号


def build_csr(n: int, m: int, edges: EdgeList) -> Csr:
    """把边表压成 CSR:点 v 的邻边占下标区间 [start[v], start[v]+deg[v]),无向边登记两次。

    邻边存两份信息:另一端点 adj_v、原始边号 adj_e(判桥、删边都要按边号来)。
    """
    deg = [0] * (n + 2)
    for u, v in edges:
        deg[u] += 1
        deg[v] += 1
    start = [0] * (n + 2)
    total = 0
    for v in range(1, n + 1):
        start[v] = total
        total += deg[v]
    start[n + 1] = total
    adj_v = [0] * (2 * m)
    adj_e = [0] * (2 * m)
    pos = start[:]  # 写入游标,初值就是每个点区间的起点
    for e, (u, v) in enumerate(edges):
        adj_v[pos[u]], adj_e[pos[u]] = v, e
        pos[u] += 1
        adj_v[pos[v]], adj_e[pos[v]] = u, e
        pos[v] += 1
    return start, adj_v, adj_e, deg


def flood(csr: Csr, n: int, ban: int, skip: bytearray | None) -> list[int]:
    """忽略 skip 中标 1 的边与被删边 ban,用 flood-fill 给连通块编号。

    skip 为空时得到的就是普通连通分量编号(flow >= 1 的判据);
    skip 是桥标记时,剩下的每个连通块就是一个边双连通分量(flow >= 2 的判据)。
    """
    start, adj_v, adj_e, deg = csr
    label = [0] * (n + 1)
    comp = 0
    for s in range(1, n + 1):
        if label[s]:
            continue
        comp += 1
        label[s] = comp
        st = [s]
        while st:
            u = st.pop()
            for i in range(start[u], start[u] + deg[u]):
                e = adj_e[i]
                removed = e == ban or (skip is not ALL_EDGES and skip[e])  # 被删边或桥
                if removed:
                    continue
                w = adj_v[i]
                if not label[w]:
                    label[w] = comp
                    st.append(w)
    return label


def two_ecc(csr: Csr, n: int, m: int, ban: int) -> list[int]:
    """删掉边 ban 后每个点所属的边双连通分量编号(ban = NO_BAN 表示不删边)。

    先迭代式 Tarjan 标出所有桥,再忽略桥与被删边 flood-fill,每块就是一个分量。
    写成迭代是为了躲开 Python 的递归深度限制——n = 3000 的链足以撑爆默认递归栈。
    """
    start, adj_v, adj_e, deg = csr
    dfn = [0] * (n + 1)   # Tarjan 时间戳,0 表示还没访问
    low = [0] * (n + 1)   # 追溯值:子树里能绕回的最早时间戳
    par = [-1] * (n + 1)  # 每个点是从父亲哪条边下来的,用来排除"原路返回"
    cur = start[:]        # 邻边游标:每个点已经扫到区间里的哪一个位置
    is_bridge = bytearray(m)
    vstk = [0] * (n + 1)  # DFS 顶点栈
    estk = [0] * (n + 1)  # 与顶点栈同高的入边栈:estk[top] 是 vstk[top] 的入边
    timer = 0
    for s in range(1, n + 1):  # 图可以不连通,逐分量起一次 DFS
        if dfn[s]:
            continue
        timer += 1
        dfn[s] = low[s] = timer
        vstk[0] = s
        estk[0] = -1
        top = 1
        while top:
            u = vstk[top - 1]
            i = cur[u]
            end = start[u] + deg[u]  # u 每轮都变,区间右端也要跟着重算
            while i < end and adj_e[i] == ban:  # 被删的边直接跳过
                i += 1
            cur[u] = i
            if i >= end:  # 回溯:u 的子树处理完毕,可以判桥了
                top -= 1
                if top:
                    p = vstk[top - 1]
                    if low[u] > dfn[p]:
                        is_bridge[estk[top]] = 1  # 树边 (p,u) 是桥
                    if low[u] < low[p]:
                        low[p] = low[u]
                continue
            cur[u] = i + 1
            e = adj_e[i]
            w = adj_v[i]
            if not dfn[w]:  # 树边:压栈,等回溯时判桥
                timer += 1
                dfn[w] = low[w] = timer
                par[w] = e
                vstk[top] = w
                estk[top] = e
                top += 1
                continue
            is_back_edge = e != par[u] and dfn[w] < low[u]  # 回边,且指向祖先
            if is_back_edge:
                low[u] = dfn[w]
    return flood(csr, n, ban, is_bridge)


def count_pairs(label: list[int]) -> int:
    """同一等价类内部的点对数之和,即 #{(i<j) : label[i] == label[j]}。

    label 的下标 0 是占位格(本题不用点 0),只统计 label[1..n],
    否则占位格会被并进类号 0 的那一类,凭空多算出若干点对。
    """
    cnt: ClassCount = {}
    for x in label[1:]:
        cnt[x] = cnt.get(x, 0) + 1
    return sum(c * (c - 1) // 2 for c in cnt.values())


def count_flow3_pairs(csr: Csr, n: int, m: int, edges: EdgeList, bel0: list[int]) -> int:
    """flow >= 3 的点对数:删掉任意一条边后两点仍同属一个边双分量。

    删「桥」不会改变原图的边双划分(删边只会让划分变细、不可能合并,而桥不在任何
    非平凡块内部),所以只检验非桥边。每轮按 (上一轮类号, 本轮分量号) 把等价类细分
    一次——这类精化只分裂、不合并,跑完所有非桥边后同类的点对恰好就是 flow >= 3。

    没有非桥边就意味着原图是森林(每条边都是桥),删一条边必然切断,cnt3 = 0。
    """
    non_bridge = [e for e, (u, v) in enumerate(edges) if bel0[u] == bel0[v]]
    if not non_bridge:
        return 0
    cls = [0] * (n + 1)  # 初值全相同,是最粗的起点
    for ban in non_bridge:
        bel = two_ecc(csr, n, m, ban)
        rank: ClassRank = {}
        for v in range(1, n + 1):
            key = cls[v] * (n + 1) + bel[v]  # 拼成一个可哈希的二元组键
            if key not in rank:
                rank[key] = len(rank)
            cls[v] = rank[key]
        if len(rank) == n:  # 类已经全是单点,再细分也不会变回来(此时 cnt3 必为 0)
            break
    return count_pairs(cls)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    edges: EdgeList = [(next(data), next(data)) for _ in range(m)]
    csr = build_csr(n, m, edges)

    bel0 = two_ecc(csr, n, m, NO_BAN)  # 原图的边双划分,后两层都要用
    cnt1 = count_pairs(flood(csr, n, NO_BAN, ALL_EDGES))                      # 连通 = flow >= 1
    cnt2 = count_pairs(bel0)                                                  # 2-边连通 = flow >= 2
    cnt3 = count_flow3_pairs(csr, n, m, edges, bel0)                          # 待删边仍 2-边连通 = flow >= 3
    print(cnt1 + cnt2 + cnt3)


if __name__ == "__main__":
    solve()

C++ 版(同一算法,用计数排序做精化):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 20:29
 * update_at: 2026-10-07 20:29
 */
// main.cpp:一本通 1731《最大流》(同 CERC 2015 J "Juice Junctions")
// 无向图每个点度数 <= 3、每条边容量 1,求所有点对 i<j 间最大流之和。
// 由最大流最小割定理:端点度为 d 的点对流不超过 min(d(u),d(v)) <= 3,故流量 ∈ {0,1,2,3}。
//   flow >= 1 <=> 两点在原图中连通(并查集);
//   flow >= 2 <=> 两点属于同一「边双连通分量」(删掉桥以后的块);
//   flow >= 3 <=> 删去任意一条边后,两点仍属同一边双连通分量。
// 记 cntk = #{(i<j) : flow(i,j) >= k},则答案 = cnt1 + cnt2 + cnt3。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 3005;             // 点数上限 3000
const int MAXM = 4505;             // 边数上限 floor(3n/2) = 4500

int n, m;                          // 点数、边数
int eu[MAXM], ev[MAXM];            // 第 i 条边的两个端点(边编号 0..m-1)

// 链式前向星:每条无向边登记两次,edgeIdx 记回原始边号
int head[MAXN], nxt[2 * MAXM], to[2 * MAXM], edgeIdx[2 * MAXM], tot;

int dfn[MAXN], low[MAXN];          // Tarjan 时间戳与追溯值
int parEdge[MAXN];                 // 每个点从父亲下来的那条边号
int cur[MAXN];                     // 迭代式 DFS 的邻接边游标
char isBridge[MAXM];               // 该边是否为原图(或删边后图)的桥
int bel[MAXN];                     // 每个点的边双连通分量编号(bel 是原图的划分,供 cnt2 与挑非桥边用)
int belNow[MAXN];                  // 删边后本轮新算出的分量编号
int stk[MAXN], estk[MAXN];         // 迭代 DFS 的顶点栈与入边栈

int cls[MAXN];                     // 等价类精化过程中的当前类编号
int ord1[MAXN], ord2[MAXN];        // 计数排序用的顺序数组
int cntArr[MAXN + 2];              // 计数排序的桶

// 加边:u、v 之间连一条编号为 id 的边
void addEdge(int id, int u, int v) {
    tot++;
    to[tot] = v;
    edgeIdx[tot] = id;
    nxt[tot] = head[u];
    head[u] = tot;
}

// 求「删去第 ban 条边」后图的边双连通分量编号,写入 out[1..n](ban < 0 表示不删边)。
// 迭代式 Tarjan 标出所有桥,再忽略桥与被删边做 flood-fill,每个连通块即一个分量。
void edgeBiconnected(int ban, int out[]) {
    for (int i = 1; i <= n; i++) {
        dfn[i] = 0;
        low[i] = 0;
        cur[i] = head[i];
        out[i] = 0;
        parEdge[i] = -1;
    }
    for (int i = 0; i < m; i++) isBridge[i] = 0;

    int timer = 0;
    for (int s = 1; s <= n; s++) {          // 图可以不连通,逐连通块 DFS
        if (dfn[s]) continue;
        int top = 0;
        dfn[s] = low[s] = ++timer;
        stk[top] = s;
        estk[top] = -1;
        top++;
        while (top > 0) {
            int u = stk[top - 1];
            if (cur[u]) {                   // 还有没走过的邻边
                int e = cur[u];
                cur[u] = nxt[e];
                int id = edgeIdx[e];
                if (id == ban) continue;    // 这条边被删掉了
                int v = to[e];
                if (!dfn[v]) {              // 树边:把 v 压栈,稍后回溯时判桥
                    dfn[v] = low[v] = ++timer;
                    parEdge[v] = id;
                    stk[top] = v;
                    estk[top] = id;
                    top++;
                } else if (id != parEdge[u] && dfn[v] < low[u]) {
                    low[u] = dfn[v];        // 回边,指向祖先
                }
            } else {                        // 回溯:u 的子树已经处理完
                top--;
                int pe = estk[top];
                if (top > 0) {
                    int p = stk[top - 1];
                    if (low[u] > dfn[p]) isBridge[pe] = 1;   // 树边 (p,u) 是桥
                    if (low[u] < low[p]) low[p] = low[u];
                }
            }
        }
    }

    int comp = 0;
    for (int s = 1; s <= n; s++) {          // 忽略桥与被删边,逐块染色
        if (out[s]) continue;
        out[s] = ++comp;
        int sp = 0;
        stk[sp++] = s;
        while (sp > 0) {
            int u = stk[--sp];
            for (int e = head[u]; e; e = nxt[e]) {
                int id = edgeIdx[e];
                if (id == ban || isBridge[id]) continue;
                int v = to[e];
                if (!out[v]) {
                    out[v] = comp;
                    stk[sp++] = v;
                }
            }
        }
    }
}

// 统计「编号相同的点对」个数:某等价关系下的点对数 C(k,2) 之和
ll countEqualPairs(int a[]) {
    static int buf[MAXN];
    for (int i = 1; i <= n; i++) buf[i - 1] = a[i];
    sort(buf, buf + n);
    ll res = 0;
    for (int i = 0; i < n; ) {
        int j = i;
        while (j < n && buf[j] == buf[i]) j++;
        ll c = j - i;
        res += c * (c - 1) / 2;
        i = j;
    }
    return res;
}

// 把等价类按 (cls, belNow) 两元组重新编号:两趟计数排序,等价类只会被细分,绝不合并。
// 好处是全程确定性(不依赖哈希),且每轮代价 O(n)。
void refine(int maxCls) {
    // 第一趟:按 belNow 稳定排序(belNow ∈ [1, n])
    for (int i = 0; i <= n + 1; i++) cntArr[i] = 0;
    for (int v = 1; v <= n; v++) cntArr[belNow[v]]++;
    int sum = 0;
    for (int i = 0; i <= n + 1; i++) {
        int c = cntArr[i];
        cntArr[i] = sum;
        sum += c;
    }
    for (int v = 1; v <= n; v++) ord1[cntArr[belNow[v]]++] = v;

    // 第二趟:在 bel 有序的基础上按 cls 稳定排序,得到 (cls, bel) 的字典序
    for (int i = 0; i <= maxCls + 1; i++) cntArr[i] = 0;
    for (int i = 0; i < n; i++) cntArr[cls[ord1[i]]]++;
    sum = 0;
    for (int i = 0; i <= maxCls + 1; i++) {
        int c = cntArr[i];
        cntArr[i] = sum;
        sum += c;
    }
    for (int i = 0; i < n; i++) ord2[cntArr[cls[ord1[i]]]++] = ord1[i];

    // 相邻两个 (cls, bel) 只要不同就开一个新类
    int r = 0;
    for (int i = 0; i < n; i++) {
        int v = ord2[i];
        if (i > 0) {
            int u = ord2[i - 1];
            if (cls[v] != cls[u] || belNow[v] != belNow[u]) r++;
        }
        cntArr[v] = r;                  // 先借用 cntArr 暂存新编号
    }
    for (int v = 1; v <= n; v++) cls[v] = cntArr[v];
}

// 并查集(路径折半),只用来数连通分量
int fa[MAXN];
int findRoot(int x) {
    while (fa[x] != x) {
        fa[x] = fa[fa[x]];
        x = fa[x];
    }
    return x;
}

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    tot = 0;
    for (int i = 1; i <= n; i++) head[i] = 0;
    for (int i = 0; i < m; i++) {
        int x, y;
        if (scanf("%d %d", &x, &y) != 2) return 0;
        eu[i] = x;
        ev[i] = y;
        addEdge(i, x, y);
        addEdge(i, y, x);
    }

    // ---- cnt1:连通分量 -> flow >= 1 的点对数 ----
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 0; i < m; i++) {
        int a = findRoot(eu[i]);
        int b = findRoot(ev[i]);
        if (a != b) fa[a] = b;
    }
    for (int i = 1; i <= n; i++) cls[i] = findRoot(i);
    ll cnt1 = countEqualPairs(cls);

    // ---- cnt2:原图的边双连通分量 -> flow >= 2 的点对数 ----
    edgeBiconnected(-1, bel);
    ll cnt2 = countEqualPairs(bel);
    // ---- cnt3:每删一条「非桥边」做一次精化 -> flow >= 3 的点对数 ----------------
    // 删掉一条桥不会改变原图的边双划分(删边只会让划分变细、不可能合并,
    // 而桥不在任何非平凡边双块的内部),所以桥无需检验。
    for (int v = 1; v <= n; v++) cls[v] = 0;
    ll cnt3 = 0;
    if (m > 0) {
        int nonBridge = 0;
        for (int i = 0; i < m; i++)
            if (bel[eu[i]] == bel[ev[i]]) nonBridge++;   // 非桥:两端点在同一分量
        if (nonBridge > 0) {
            int maxCls = 0;
            for (int ban = 0; ban < m; ban++) {
                if (bel[eu[ban]] != bel[ev[ban]]) continue;   // 桥跳过
                edgeBiconnected(ban, belNow);
                refine(maxCls);
                maxCls = 0;
                for (int v = 1; v <= n; v++)
                    if (cls[v] > maxCls) maxCls = cls[v];
                if (maxCls == n - 1) break;   // 全是单点,再分下去 cnt3 必然是 0
            }
            cnt3 = countEqualPairs(cls);
        }
    }

    printf("%lld\n", cnt1 + cnt2 + cnt3);
    return 0;
}

复杂度

  • 时间:本层的划分各自都是 O(n+m)O(n+m) 的 Tarjan/flood-fill;cnt1\mathrm{cnt}_1 那一层 在 C++ 里用并查集 O((n+m)α)O((n+m)\alpha)、在 Python 里就是一次 flood-fill O(n+m)O(n+m); cnt3\mathrm{cnt}_3 最多做 mm 轮,总计 O(m(n+m))O(m(n+m))。最坏数据 n=3000,m=4500n = 3000, m = 4500 时约 3.4×1073.4 \times 10^7 次基本操作,C++ 实测 0.20 s,远低于 3 s 限时。
  • 空间:邻接表 O(n+m)O(n+m),Tarjan 的 dfn/low/cur、bel、cls 等各 O(n)O(n), 总计 O(n+m)O(n+m),n=3000n = 3000 时不到 1 MB,与 256 MB 的限值差得很远。
  • 与 C++ 解法的关系:main.cpp 与 main.py 是同一算法(三层判据、精化轮数都相同), 只是把 Python 的 dict 去重换成了 C++ 的两趟计数排序、把 Python 的 flood-fill 连通分量换成了 C++ 的并查集。
  • Python 的 TLE 风险:算法同阶,但 CPython 的解释器常数大,mm 轮 Tarjan 的实测耗时 在顶格数据(n=3000,m=4500n = 3000, m = 4500)上约 8 s,会超过 3 s 的限时;中等规模 (n⩽1000n \leqslant 1000)在一秒内。按 oj-python-style 的约定,这里允许 Python TLE, 但算法不允许降级——所以 Python 版仍是 O(m(n+m))O(m(n+m)) 的 Tarjan 精化, 而不是退化成枚举点对求最大流。

总结

  • 先用割的大小卡住值域。 “度数不超过 33"这句约束的全部价值在于把答案从 O(n2)O(n^2) 个 小整数压成 {0,1,2,3}\{0,1,2,3\} 四档;一旦想到"答案 =cnt1+cnt2+cnt3= \mathrm{cnt}_1 + \mathrm{cnt}_2 + \mathrm{cnt}_3”, 逐对求最大流的 101110^{11} 就瓦解了。
  • 三层判据都是连通性的变体。 连通(并查集)→ 22-边连通(边双分量)→ “删任意一条边后仍 22-边连通”(mm 次边双划分的交)。Menger 定理把"边不相交路径数" 和"最小割大小"在每一层上对应起来,所以三个 ⩾k\geqslant k 的判定全都只依赖图的划分结构。
  • 数点对就是数等价类。 三层的答案都是同一句话:“在某等价关系下同编号的点对数”, 于是三处代码可以共用同一个计数函数,这也是本题代码能压得很短的原因。
  • 迭代式 Tarjan。 Python 默认递归深度只有约 10001000,n=3000n = 3000 的链就会爆栈; 用显式栈写 Tarjan 是本题 Python 版能跑通的必要条件,同时也顺手绕开了 C++ 的爆栈风险。

关于本题数据的说明

本题的测试数据由素材源目录里的 data.py(基于 cyaron 的分层生成器)自造, 而非官方原题数据,题面也属网络重建;生成器对每组数据都给出了独立的闭式期望答案, 与前文三层判据的推导一致(例如点 10 是 n=mn = m 双顶格的棱柱 C1500×K2C_{1500} \times K_2, 33-边连通故答案恰为理论上界 3(30002)=13 495 5003\binom{3000}{2} = 13\,495\,500)。 因此 main.cpp 与 main.py 在本目录数据上的通过,只说明实现与题面的推导自洽, 不等价于官方数据 AC。

图示解析

三层判据在一张「稠密块 + 桥」的图上表现最清楚:块内点对流量高,跨桥点对流量掉到 11。

flowchart LR
    subgraph K4["点 1,2,3,4 构成 K4"]
    A["1"] --- B["2"]
    A --- C["3"]
    A --- D["4"]
    B --- C
    B --- D
    C --- D
    end
    D --- E["5"]
    E --- F["6"]

1,2,3,41,2,3,4 四点两两相连,构成 33-正则且 33-边连通的 K4K_4,块内任意两点的流量都是 33 (⩾3\geqslant 3 来自 33-边连通:删掉任意两条边仍连通;⩽3\leqslant 3 来自度数只有 33)。 边 44-55 与 55-66 都是桥,所以点 55、66 与其余四点的流量都只有 11。 对照三层判据:cnt1\mathrm{cnt}_1 把 55、66 也算进来(连通就有流量 11), cnt2\mathrm{cnt}_2 把它们排除(它们各自单独成块),cnt3\mathrm{cnt}_3 则把「K4K_4 内部」 与「只靠两条边相连」区分开——层与层之间的差就构成答案。 以这张图为例(n=6n=6):cnt1=(62)=15\mathrm{cnt}_1 = \binom{6}{2} = 15, cnt2=(42)=6\mathrm{cnt}_2 = \binom{4}{2} = 6,cnt3=6\mathrm{cnt}_3 = 6,答案 15+6+6=2715 + 6 + 6 = 27。