「朋友圈」最大团问题题解

问题分析

我们需要在 $A$ 国和 $B$ 国的人中找到一个最大的朋友圈，其中：

• $A$ 国人之间：当 $(a \oplus b) \bmod 2 = 1$ 时是朋友
• $B$ 国人之间：当 $(a \oplus b) \bmod 2 = 0$ 或 $\text{popcount}(a \mid b)$ 为奇数时是朋友
• $A$、$B$ 国人之间：由输入给出朋友关系

这实际上是一个最大团问题，但由于数据规模较大，需要特殊方法解决。

核心思路

利用二分图匹配和网络流来求解最大团。关键观察是：

1. $A$ 国人之间的朋友关系构成一个二分图（按友善值奇偶性划分）
2. 对于固定的 $A$ 国子集，$B$ 国人的选择可以转化为独立集问题

算法详解

1. 朋友关系分析

// A国人之间：只有奇偶性不同才是朋友
if ((a[i]^a[j]) & 1 ^ 1) continue;

// B国人之间：需要满足复杂条件
if ((b[i]^b[j]) & 1 ^ 1) continue;  // 奇偶性相同
if (popcount(b[i] | b[j]) & 1) continue;  // 按位或的popcount为奇数

2. 网络流建模

对于固定的 $A$ 国子集，构建二分图：

int Query(int x, int y) {
    // S -> 偶数B国人 -> 奇数B国人 -> T
    for (int i = 1; i <= B; i++) {
        if (!adm[x][i] || !adm[y][i]) continue;  // 必须与所有选中的A国人是朋友
        
        if (b[i] & 1)
            addedge(i, T, 1);  // 奇数B国人连向汇点
        else
            addedge(S, i, 1);  // 偶数B国人从源点连出
            
        // 处理B国人之间的非朋友关系
        for (int j = i + 1; j <= B; j++) {
            if (!adm[x][j] || !adm[y][j]) continue;
            if ((b[i]^b[j]) & 1 ^ 1) continue;
            if (popcount(b[i] | b[j]) & 1) continue;
            
            // 在非朋友之间建立容量为INF的边
            if (b[j] & 1)
                addedge(i, j, INF);
            else
                addedge(j, i, INF);
        }
    }
    
    // 最小割 = 最大独立集的补集
    int rtn = total_B;  // 初始包含所有符合条件的B国人
    while (bfs()) {
        rtn -= dfs(S, INF);
    }
    return rtn;
}

3. 枚举A国子集

// 情况1：不选任何A国人
ans = Query(0, 0);

// 情况2：只选一个A国人
for (int i = 1; i <= A; i++) {
    ans = max(ans, Query(i, i) + 1);
}

// 情况3：选两个A国人（必须是朋友）
for (int i = 1; i <= A; i++) {
    for (int j = i + 1; j <= A; j++) {
        if ((a[i]^a[j]) & 1 ^ 1) continue;  // 不是朋友则跳过
        ans = max(ans, Query(i, j) + 2);
    }
}

算法正确性

为什么使用网络流？

1. 问题转化：对于固定的 $A$ 国子集，在 $B$ 国中找最大团等价于在补图中找最大独立集
2. 二分图性质：$B$ 国人按友善值奇偶性自然形成二分图
3. 最小割应用：在二分图中，最大独立集 = 总点数 - 最小顶点覆盖

网络流建模细节

• 源点S：连接所有偶数 $B$ 国人
• 汇点T：所有奇数 $B$ 国人连接汇点
• INF边：在非朋友之间建立不可割的边
• 容量1：每个 $B$ 国人的点权为1

复杂度分析

• 枚举A国子集：$O(A^2)$
• 每次网络流：$O(B^3)$ 但实际运行很快
• 总复杂度：$O(A^2 \cdot B^3)$，在数据范围内可接受

样例验证

样例输入：

A=2, B=4
a = [1, 2]  
b = [2, 6, 5, 4]

处理过程：

1. 枚举所有A国子集组合
2. 对每个组合，构建对应的B国人网络流图
3. 计算最大团大小
4. 最终找到最大团为5（A国2人 + B国3人）

总结

本题的巧妙之处在于：

1. 问题分解：将复杂的朋友圈问题分解为A国枚举 + B国网络流
2. 图论转化：利用最大团与最大独立集的对偶关系
3. 网络流应用：用最小割求解最大独立集
4. 优化枚举：利用A国规模小的特点进行枚举

这种"枚举小集合 + 网络流处理大集合"的方法在解决组合优化问题时非常有效。