Love Polygon 问题详细题解

问题描述

有 n 个人，每个人喜欢另一个人（可以有多人喜欢同一人）。要求选择最少的人进行"配对"，使得：

1. 如果选择了 A->B，那么 A 和 B 都被覆盖
2. 每个人只能被覆盖一次
3. 覆盖所有人

核心思路

1. 模型转化

将问题转化为有向图：

• 每个人是顶点
• "喜欢关系"是有向边
• 每个顶点出度为1（每个人只喜欢一个人）
• 入度可以任意（可以被多人喜欢）

这样的图称为功能图(Functional Graph)，由若干个基环树组成。

2. 关键观察

目标：在功能图中选择最少的边，使得：

• 每个顶点恰好被一条选中的边覆盖
• 选中的边形成匹配（不共享端点）

这等价于在功能图中找最小边覆盖。

算法步骤详解

步骤1：建图与预处理

unordered_map<string, int> num;  // 名字映射到ID
vector<int> nxt;  // 每个人喜欢的人
vector<int> d;    // 入度

// 检查双向喜欢
pair<int, int> rev_edge = make_pair(v, u);
if (vis.count(rev_edge)) {
    del[v] = del[u] = true;  // 标记为已配对
}

双向喜欢处理：如果 A->B 且 B->A，可以直接配对。

步骤2：奇偶性检查

if (n % 2 == 1) {
    cout << -1 << endl;
    return;
}

总人数必须是偶数，因为每对覆盖2人。

步骤3：拓扑排序处理链

// 入度为0的顶点入队
for (int i = 1; i <= n; i++) {
    if (d[i] == 0) q.push(i);
}

while (!q.empty()) {
    int t = q.front(); q.pop();
    
    if (!del[nxt[t]] && !del[t]) {
        del[t] = del[nxt[t]] = true;  // 配对
        ans++;
    }
    
    d[nxt[t]]--;  // 减少入度
    
    if (d[nxt[t]] == 0) q.push(nxt[t]);
}

贪心策略：

1. 找到入度为0的顶点（链的开端）
2. 与它指向的人配对
3. 更新入度，继续处理

正确性证明：入度为0的顶点只能作为起点，优先配对不会使结果变差。

步骤4：处理剩余的环

经过拓扑排序后，图中只剩下环。

使用并查集合并连通分量

// 初始化并查集
for (int i = 1; i <= n; i++) {
    if (!del[i]) {
        siz[i] = 1;
        fa[i] = i;
    }
}

// 合并连通分量
for (int i = 1; i <= n; i++) {
    if (!del[i] && !del[nxt[i]]) {
        int fx = find(i), fy = find(nxt[i]);
        
        if (fx == fy) {
            cir[fx] = true;  // 发现环
            continue;
        }
        
        fa[fx] = fy;
        siz[fy] += siz[fx];
    }
}

步骤5：计算环的答案

对于每个连通分量：

if (cir[fx]) {  // 环的情况
    if (siz[fx] == 2) {
        ans += 0;  // 双向喜欢已处理
    } else if (siz[fx] % 2 == 0) {
        ans += siz[fx] / 2;  // 偶数环：完美匹配
    } else {
        ans += siz[fx] / 2 + 1;  // 奇数环：需要多一个
    }
} else {  // 链的情况
    if (siz[fx] % 2 == 0) {
        ans += siz[fx] / 2;
    } else {
        ans += siz[fx] / 2 + 1;
    }
}

分情况讨论

情况1：简单链

A -> B -> C -> D

处理：

1. A入度为0，配对A-B
2. C入度变为0，配对C-D 结果：2对

情况2：双向喜欢

A <-> B   C -> D -> E

处理：

1. A-B双向喜欢，直接配对（不计入答案）
2. C入度为0，配对C-D
3. E入度变为0，但已无配对对象 结果：1对

情况3：环

偶数环（4个顶点）

A -> B -> C -> D -> A

最少需要2对：

• 方案1：A-B, C-D
• 方案2：B-C, D-A

奇数环（3个顶点）

A -> B -> C -> A

最少需要2对：

• 无法完美匹配
• 方案：A-B，C需要与环外配对

情况4：基环树

    D
    ↓
A → B → C
    ↻

处理：先处理链部分，再处理环。

算法证明

贪心正确性

引理1：入度为0的顶点必须与它指向的顶点配对。

证明：

• 设顶点A入度为0
• A只能通过边 A->B 被覆盖
• 如果不选这条边，A无法被覆盖
• 因此必须选择 A->B

引理2：优先处理入度为0的顶点不会使结果变差。

证明：

• 处理入度为0的顶点后，可能产生新的入度为0的顶点
• 继续贪心处理，最终得到最优解
• 如果延迟处理，可能导致更差的匹配

环的处理正确性

对于大小为 k 的环：

• 如果 k 是偶数：可以完美匹配，需要 k/2 对
• 如果 k 是奇数：无法完美匹配，需要 (k+1)/2 对

证明：

• 在环上，每条边覆盖两个顶点
• 要覆盖所有顶点，至少需要 ceil(k/2) 条边
• 这个下界是可以达到的

复杂度分析

• 时间复杂度：O(nα(n))

  • 建图：O(n)
  • 拓扑排序：O(n)
  • 并查集操作：O(nα(n))
  • 总体：O(nα(n))

• 空间复杂度：O(n)

  • 存储图：O(n)
  • 并查集：O(n)
  • 队列：O(n)

示例分析

示例1

输入：
3
Alice Bob
Bob Charlie
Charlie Alice

图：
Alice -> Bob -> Charlie -> Alice (3环)

处理：
1. 检查奇偶性：n=3是奇数，输出-1

示例2

输入：
4
A B
B C
C D
D B

图：
A -> B <- D
     ↓    ↺
     C

处理：
1. A入度为0，配对A-B
2. 剩余：B<-D, B->C
3. 形成环D->B->C（3环）
4. 需要2对配对
结果：1 + 2 = 3

边界情况

自环

A -> A

需要单独处理，通常需要额外配对。

多个连通分量

算法能正确处理多个独立的环和链。

大环

使用并查集可以高效处理大环。

代码优化建议

1. 正确使用变量：

// 应该使用cnt（顶点数）而不是n（边数）
for (int i = 1; i <= cnt; i++) {  // 而不是 <= n
    // ...
}

2. 改进双向喜欢处理：

if (vis.count(rev_edge)) {
    // 应该增加ans，因为这是一对有效的配对
    if (!del[u] && !del[v]) {
        del[u] = del[v] = true;
        ans++;  // 增加计数器
    }
}

3. 简化环处理： 可以直接遍历环而不需要使用并查集：

vector<bool> visited(cnt + 1, false);
for (int i = 1; i <= cnt; i++) {
    if (!del[i] && !visited[i]) {
        // 找环
        int u = i;
        vector<int> cycle;
        while (!del[u] && !visited[u]) {
            visited[u] = true;
            cycle.push_back(u);
            u = nxt[u];
        }
        // 处理环
        if (cycle.size() > 0) {
            // 计算答案
        }
    }
}

总结

Love Polygon 问题是一个经典的功能图匹配问题，核心在于：

1. 识别图结构：功能图 = 链 + 环
2. 贪心策略：优先处理链的开端
3. 分治处理：分别处理链和环
4. 数学计算：环的最小匹配数 = ceil(环大小/2)

算法巧妙地将复杂问题分解为简单的子问题，通过贪心和数学计算得到最优解。