通讯录分组问题题解

一、题目分析

题目要求将通讯录分组，使得每个朋友只能属于其允许的组，且最大组的大小最小。关键条件：

1. 每个朋友必须被分配到一个允许的组；
2. 目标是最小化最大组的大小。

二、算法思路

1. 二分查找+最大流验证：

   • 二分枚举最大组的可能大小mid；
   • 对于每个mid，使用最大流算法验证是否能在限制下完成分组。

2. 网络流建模：

   • 源点连接所有朋友，容量为1（每个朋友只能被分配一次）；
   • 朋友节点连接其允许的组，容量为1；
   • 组节点连接汇点，容量为mid（限制组的最大大小）。

3. 最大流验证：

   • 若最大流等于朋友数N，说明所有朋友可被分配，mid可行；
   • 否则，mid太小，需增大。

三、代码实现

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<sstream>
using namespace std;

const int MAXM = 900000;
const int MAXN = 2000;
const int INF = 0x3f3f3f3f;

struct Edge {
    int to, cap, next;
};

Edge edge[MAXM];
int level[MAXN];
int head[MAXN];
int group[MAXN][MAXN];  // 存储每个朋友允许的组
int src, des, cnt;      // 源点、汇点、边计数器

// 添加双向边（正向容量cap，反向容量0）
void addedge(int from, int to, int cap) {
    edge[cnt].to = to;
    edge[cnt].cap = cap;
    edge[cnt].next = head[from];
    head[from] = cnt++;
    
    swap(from, to);  // 反向边
    
    edge[cnt].to = to;
    edge[cnt].cap = 0;
    edge[cnt].next = head[from];
    head[from] = cnt++;
}

// BFS构建层次图
int bfs() {
    memset(level, -1, sizeof level);
    queue<int> q;
    q.push(src);
    level[src] = 0;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if (edge[i].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[des] != -1;
}

// DFS寻找增广路径
int dfs(int u, int f) {
    if (u == des) return f;
    int tem;
    
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].to;
        if (edge[i].cap > 0 && level[v] == level[u] + 1) {
            tem = dfs(v, min(f, edge[i].cap));
            if (tem > 0) {
                edge[i].cap -= tem;
                edge[i ^ 1].cap += tem;  // 反向边增加流量
                return tem;
            }
        }
    }
    level[u] = -1;  // 标记此节点已无法扩展
    return 0;
}

// Dinic算法计算最大流
int Dinic() {
    int ans = 0, tem;
    while (bfs()) {  // 不断构建层次图
        while ((tem = dfs(src, INF)) > 0) {  // 不断寻找增广路径
            ans += tem;
        }
    }
    return ans;
}

int main() {
    int n, m;
    src = 0;       // 源点
    des = 1980;    // 汇点
    string str;
    
    while (cin >> n >> m && n && m) {
        getchar();  // 处理换行符
        
        // 读取每个朋友允许的组
        for (int i = 1; i <= n; i++) {
            getline(cin, str);
            stringstream ss(str);
            ss >> str;  // 朋友名字（忽略）
            
            int g;
            int num = 0;
            while (ss >> g) {
                group[i][++num] = g;
            }
            group[i][0] = num;  // 记录允许的组数量
        }
        
        // 二分查找最小的最大组大小
        int low = 0, high = INF - 1;
        int ans = -1;
        
        while (low <= high) {
            int mid = (low + high) / 2;
            memset(head, -1, sizeof head);
            cnt = 0;
            
            // 构建网络流图
            for (int i = 1; i <= n; i++) {
                addedge(src, i, 1);  // 源点→朋友，容量1
            }
            
            for (int i = 1; i <= m; i++) {
                addedge(i + 1000, des, mid);  // 组→汇点，容量mid
            }
            
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= group[i][0]; j++) {
                    addedge(i, group[i][j] + 1001, 1);  // 朋友→允许的组，容量1
                }
            }
            
            // 计算最大流并验证
            if (Dinic() < n) low = mid + 1;  // 无法分配所有朋友
            else {
                ans = mid;
                high = mid - 1;  // 尝试更小的mid
            }
        }
        cout << ans << endl;
    }
    return 0;
}

四、代码解释

1. 网络流构建：

   • **源点（0）**连接所有朋友节点（1~N），容量为1；
   • 朋友节点连接其允许的组节点（1001~1000+M），容量为1；
   • 组节点连接汇点（1980），容量为当前枚举的mid。

2. Dinic算法：

   • 使用BFS构建层次图，DFS寻找增广路径；
   • 最大流等于N时，表示所有朋友可被分配。

3. 二分查找：

   • 初始范围[0, INF-1]，逐步缩小范围至最小可行的mid。

五、示例解析

输入样例1：

3 2  
John 0 1  
Rose 1  
Mary 1  

1. 网络流建模：

   • 源点→John（1）、Rose（2）、Mary（3），容量均为1；
   • John→组0（1001）、组1（1002），容量为1；
   • Rose、Mary→组1（1002），容量为1；
   • 组0、组1→汇点，容量为枚举的mid。

2. 二分查找：

   • 当mid=1时，最大流为2（无法分配所有3人）；
   • 当mid=2时，最大流为3，可行。

3. 输出：

   2  
   

六、复杂度分析

• 时间复杂度：O(logN × Dinic)，其中Dinic的时间复杂度为O(V²E)；
• 空间复杂度：O(V+E)，V为节点数，E为边数。

七、关键技巧

1. 二分查找与最大流结合：将最小化最大值问题转化为可行性验证；
2. 网络流建模：通过容量限制实现分组约束；
3. Dinic算法：高效计算最大流，适用于稀疏图。