题解：新型城市化与最大团优化

题目描述

Anihc 国有 $n$ 座城市，城市之间存在着贸易合作关系。如果城市 $x$ 和城市 $y$ 之间存在贸易协定，那么它们是一对贸易伙伴。题目保证当前的城市关系可以恰好划分为不超过两个城市群，这意味着原图是一个二分图。

我们需要选择两个目前不是贸易伙伴的城市，建立新的贸易关系，使得建立关系后最大城市群的大小至少比之前增加 $1$。

城市群定义：城市群中的城市两两都是贸易伙伴，即形成一个完全子图（团）。

问题分析

关键观察

1. 二分图性质：题目保证原图可以划分为不超过两个城市群，这意味着原图是一个二分图。

2. 最大团与最大独立集的关系：

   • 在任意图中：$\text{最大团} = \text{补图的最大独立集}$
   • 在二分图中：$\text{最大独立集} = n - \text{最大匹配}$

3. 问题转化：

   • 原图 $G$ 是一个二分图
   • 我们要在补图 $G'$ 中选择一条边加入原图 $G$
   • 使得新图的最大团大小增加至少 $1$

核心转化

设原图 $G$ 的最大团大小为 $\omega(G)$，新图 $G''$（加入一条边后）的最大团大小为 $\omega(G'')$。

我们要满足：

$$\omega(G'') \geq \omega(G) + 1$$

由于在二分图中：

• $\omega(G) = \text{补图的最大独立集大小}$
• 而补图的最大独立集大小 = $n - \text{原图的最大匹配数}$

因此：

$$\omega(G) = n - M(G)$$

其中 $M(G)$ 是原图 $G$ 的最大匹配数。

条件转化为：

$$n - M(G'') \geq n - M(G) + 1$$

即：

$$M(G'') \geq M(G) + 1$$

结论：问题转化为在二分图中，加入哪些非边（补图中的边）可以使最大匹配数增加。

算法详解

1. 二分图染色与建图

void dfs(int u, int c = 0) {
    vis[u] = 1;
    // 左部点连源点，右部点连汇点
    if (c) F.add(S, u, 1);
    else F.add(u, T, 1);
    
    for (int v : G[u]) {
        if (u < v)  // 避免重复记录边
            e[++tot] = {u, v, c ? F.add(u, v, 1) : F.add(v, u, 1)};
        if (!vis[v]) dfs(v, c ^ 1);  // 交替染色
    }
}

• 对每个连通分量进行二分图染色，确定左右部点
• 左部点连源点 $S$，容量为 $1$
• 右部点连汇点 $T$，容量为 $1$
• 原图中的边：从左部点到右部点，容量为 $1$

2. 最大流求最大匹配

使用 Dinic 算法求解二分图最大匹配：

int solve(int s, int t) {
    int res = 0;
    st = s, ed = t;
    while (BFS()) {
        for (int i = 1; i <= MaxPoint; i++) 
            work[i] = head[i];
        res += DFS(st, inf);
    }
    return res;
}

3. 残量网络与强连通分量

在求得最大匹配后，构建残量网络：

对于原图中的边 $(u,v)$：

• 如果边在匹配中：正向边容量为 $0$，反向边容量为 $1$
• 如果边不在匹配中：正向边容量为 $1$，反向边容量为 $0$

在残量网络上运行 Tarjan 算法求强连通分量：

void tarjan(int u) {
    stk[++tp] = u;
    dfn[u] = low[u] = ++tt;
    
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v, w = e[i].w;
        if (!w) continue;  // 只考虑容量不为0的边
        
        if (!dfn[v]) {
            tarjan(v);
            cmin(low[u], low[v]);
        } else if (!scc[v]) {
            cmin(low[u], dfn[v]);
        }
    }
    
    if (low[u] == dfn[u]) {
        cnt++;
        while (true) {
            int v = stk[tp--];
            scc[v] = cnt;
            if (u == v) break;
        }
    }
}

4. 可行边判定定理

关键定理：一条非边 $(u,v)$ 是可行的（能使最大匹配增加）当且仅当：

1. 该边不在当前匹配中（残量网络中正向边容量为 $1$）
2. 该边的两个端点 $u$ 和 $v$ 不在同一个强连通分量中

for (int i = 1; i <= m; i++) {
    if (F.e[e[i].id].w && !F.CheckInCycle(e[i].u, e[i].v))
        id.push_back(i);
}

5. 算法正确性证明

为什么这样判断？

在残量网络中：

• 如果 $u$ 和 $v$ 在同一个 SCC 中，说明存在交替路径可以调整匹配，但不会增加总匹配数
• 如果 $u$ 和 $v$ 不在同一个 SCC 中，且边不在当前匹配中，加入这条边可以找到一条增广路，从而增加匹配数

形式化证明：

设当前最大匹配为 $M$，考虑加入边 $(u,v)$：

1. Case 1: $u$ 和 $v$ 在同一个 SCC 中

   • 存在路径 $u \rightsquigarrow v$ 在残量网络中
   • 可以通过调整得到不同的匹配，但大小仍为 $M$
   • 匹配数不增加

2. Case 2: $u$ 和 $v$ 不在同一个 SCC 中，且边不在匹配中

   • 存在从 $S$ 到 $u$ 和从 $v$ 到 $T$ 的路径
   • 边 $(u,v)$ 连接了这两条路径，形成增广路
   • 匹配数可以增加 $1$

复杂度分析

各步骤复杂度：

1. 二分图染色：$O(n + m)$
2. Dinic 算法：$O(\sqrt{n} \cdot m)$
   • 在单位容量的二分图中，Dinic 算法的复杂度为 $O(\sqrt{n} \cdot m)$
3. Tarjan 算法：$O(n + m)$
4. 可行边检查：$O(m)$

总复杂度：

$$O(\sqrt{n} \cdot m)$$

在数据范围 $n \leq 10^4, m \leq 1.5 \times 10^5$ 内可以接受。

样例分析

输入：

5 3
1 5
2 4  
2 5

解释：

• 有 $5$ 个城市，$3$ 对非贸易关系
• 原图是二分图，最大匹配为 $2$
• 最大团大小 = $5 - 2 = 3$

可行边：

• 边 $(1,5)$：可以使最大匹配增加到 $3$，最大团增加到 $4$
• 边 $(2,4)$：可以使最大匹配增加到 $3$，最大团增加到 $4$
• 边 $(2,5)$：不能增加最大匹配

输出：

2
1 5
2 4

实现细节

1. 数据结构设计

struct Maximum_flow {
    int head[MAXN], work[MAXN], dis[MAXN], Q[MAXN], tot;
    struct edge {
        int v, w, nxt;
    } e[MAXM << 1];
    // 网络流相关函数...
    
    // 强连通分量相关
    int dfn[MAXN], low[MAXN], stk[MAXN], tt, tp, scc[MAXN], cnt;
};

2. 边记录技巧

e[++tot] = {u, v, c ? F.add(u, v, 1) : F.add(v, u, 1)};

记录每条原图边对应的网络流边ID，便于后续检查残量。

3. 字典序输出

sort(e + 1, e + m + 1, [&](edge x, edge y) {
    return x.u != y.u ? x.u < y.u : x.v < y.v;
});

确保输出结果按字典序排列。

总结

本题综合运用了多个重要的图论概念和算法：

核心知识点：

1. 二分图性质：最大团、最大独立集、最大匹配的关系
2. 网络流：Dinic 算法求解二分图最大匹配
3. 残量网络：理解匹配的残余结构
4. 强连通分量：Tarjan 算法识别可调整的路径
5. 增广路理论：Hall 定理的扩展应用

算法创新点：

• 将最大团问题转化为最大匹配问题
• 利用残量网络的 SCC 分解识别可行边
• 结合网络流和图论的高效解法

实际意义：

这种方法不仅解决了本题，还提供了处理二分图匹配敏感性分析的一般框架，可用于：

• 网络可靠性分析
• 匹配稳定性研究
• 图修改问题的求解

本题展示了如何通过深刻的图论洞察，将复杂的最优化问题转化为经典算法问题，是竞赛图论中的典范题目。