AcWing 2324. 生活的艰辛 题解
题目分析
本题中约翰是公司CEO，公司股东决定让他儿子斯科特成为经理，约翰为防止儿子威胁到自己的职位，想给儿子安排管理难度系数最大的团队。公司有(n)名员工，(m)对两两矛盾关系，团队的管理难度系数为团队中矛盾关系对数除以团队总人数，需要找出管理难度系数最大的团队。
解题思路
本题可通过二分答案结合网络流的方法来求解。二分管理难度系数的值，对于每个二分的值(g)，构建一个网络流图，通过判断该网络流图的最大流情况，来确定当前二分的值是否可行，从而不断缩小范围，找到最大的管理难度系数。同时，在找到最大管理难度系数后，通过深度优先搜索（DFS）找出对应的团队成员。
代码逐段分析
- 头文件和全局变量定义
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = (1000 + N * 2) * 2, INF = 1e8;
int n, m, S, T;
int h[N], e[M], ne[M], idx;
double f[M];
int q[N], d[N], cur[N];
int dg[N];
struct Edge
{
int a, b;
}edges[M];
int ans;
bool st[N];
- 引入必要的头文件，用于输入输出、字符串操作和算法相关功能。
- 定义常量(N)（最大员工数）、(M)（最大边数）、(INF)（无穷大）。
- 变量(n)表示员工数量，(m)表示矛盾关系的对数，(S)为源点，(T)为汇点。
- (h)、(e)、(ne)、(idx)用于构建邻接表存储图的边，(f)数组记录边的容量。
- (q)、(d)、(cur)用于广度优先搜索（BFS）和增广路径查找。
- (dg)数组记录每个员工的矛盾关系数量。
- (Edge)结构体用于存储矛盾关系的两个员工，(edges)数组存储所有矛盾关系。
-
(ans)记录团队人数，(st)数组标记员工是否在团队中。
-
添加边函数
void add(int a, int b, double c1, double c2)
{
e[idx] = b, f[idx] = c1, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = c2, ne[idx] = h[b], h[b] = idx ++ ;
}
在图中添加一条从(a)到(b)容量为(c1)的边，同时添加反向边（容量为(c2)）用于网络流的反向增广。
- 构建网络流图函数
void build(double g)
{
memset(h, -1, sizeof h);
idx = 0;
for (int i = 0; i < m; i ++ ) add(edges[i].a, edges[i].b, 1, 1);
for (int i = 1; i <= n; i ++ )
{
add(S, i, m, 0);
add(i, T, m + g * 2 - dg[i], 0);
}
}
- 初始化邻接表，将(h)数组所有元素设为(-1)，(idx)设为(0)。
- 遍历所有矛盾关系，在图中添加边，容量都设为(1)。
-
遍历所有员工，从源点(S)向每个员工连边，容量为(m)；从每个员工向汇点(T)连边，容量为(m + g * 2 - dg[i])，其中(g)是当前二分的管理难度系数。
-
BFS函数（构建层次图）
bool bfs()
{
int hh = 0, tt = 0;
memset(d, -1, sizeof d);
q[0] = S, d[S] = 0, cur[S] = h[S];
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int ver = e[i];
if (d[ver] == -1 && f[i] > 0)
{
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if (ver == T) return true;
q[ ++ tt] = ver;
}
}
}
return false;
}
使用BFS构建层次图，标记每个节点的层次。若能到达汇点(T)，则返回(true)，表示存在从源点到汇点的路径；否则返回(false)。
- 增广路径查找函数
double find(int u, double limit)
{
if (u == T) return limit;
double flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i])
{
cur[u] = i;
int ver = e[i];
if (d[ver] == d[u] + 1 && f[i] > 0)
{
double t = find(ver, min(f[i], limit - flow));
if (t <= 0) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
在层次图中从节点(u)开始，沿着层次递增的路径寻找增广路径。若到达汇点(T)，则返回当前的流量限制(limit)。在遍历边的过程中，若满足层次关系且边有剩余容量，则递归地在子节点中寻找增广路径，并更新边的容量。若某条路径无法继续增广，则将该节点的层次标记为(-1)。
- Dinic算法函数
double dinic(double g)
{
build(g);
double r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}
根据给定的管理难度系数(g)构建网络流图，然后不断调用BFS和find函数，计算最大流并返回。
- DFS函数
void dfs(int u)
{
st[u] = true;
if (u != S) ans ++ ;
for (int i = h[u]; ~i; i = ne[i])
{
int ver = e[i];
if (!st[ver] && f[i] > 0)
dfs(ver);
}
}
深度优先搜索函数，从源点(S)开始，标记访问过的节点（员工），并统计团队人数。如果当前节点不是源点，则团队人数(ans)加(1)。然后遍历当前节点的所有邻边，对未访问且边容量大于(0)的节点继续进行DFS。
- 主函数
int main()
{
scanf("%d%d", &n, &m);
S = 0, T = n + 1;
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
dg[a] ++, dg[b] ++ ;
edges[i] = {a, b};
}
double l = 0, r = m;
while (r - l > 1e-8)
{
double mid = (l + r) / 2;
double t = dinic(mid);
if (m * n - t > 0) l = mid;
else r = mid;
}
dinic(l);
dfs(S);
if (!ans) puts("1\n1");
else
{
printf("%d\n", ans);
for (int i = 1; i <= n; i ++ )
if (st[i])
printf("%d\n", i);
}
return 0;
}
- 读取员工数量(n)和矛盾关系对数(m)，设置源点(S = 0)和汇点(T = n + 1)。
- 读取所有矛盾关系，更新每个员工的矛盾关系数量，并存储到(edges)数组中。
- 初始化二分的左右边界(l = 0)，(r = m)。在二分过程中，计算中间值(mid)，调用(dinic(mid))计算在该管理难度系数下的最大流(t)。若(m * n - t > 0)，说明当前(mid)偏小，更新左边界(l = mid)；否则更新右边界(r = mid)。
- 找到最大管理难度系数(l)后，再次调用(dinic(l))构建网络流图，然后调用(dfs(S))找出团队成员。
- 根据(ans)的值输出结果。若(ans = 0)，输出(1)和(1)；否则，先输出团队人数(ans)，再依次输出团队中每个员工的编号。
时间复杂度分析
- 二分的次数大约为(O(\log(\frac{R - L}{\epsilon})))，其中(R)是右边界，(L)是左边界，(\epsilon)是精度。
- 每次二分调用(dinic)函数，(dinic)函数中构建网络流图的时间复杂度为(O(n + m))，计算最大流的时间复杂度为(O(n^2m))（这里(n)是员工数量，(m)是矛盾关系对数）。
- 总的时间复杂度为(O(\log(\frac{R - L}{\epsilon}) \times n^2m))。
空间复杂度分析
- 图的存储使用邻接表，边数为(m)，所以存储图的空间复杂度为(O(m))。
- 其他辅助数组如(q)、(d)、(cur)、(dg)、(st)等，大小与员工数量(n)有关，为(O(n))。
- 总的空间复杂度为(O(n + m))。
