AcWing 961. 最大获利 题解
题目分析
本题中CS&T通讯公司要在N个可选地址建立通讯中转站，每个中转站有建立成本。同时存在M个用户群，每个用户群依赖两个中转站通讯，使用这些中转站公司可获得一定收益。目标是选择建立合适的中转站，使公司的净获利（收益之和 - 成本之和）最大。
最大权闭合图代码实现思路
将问题转化为最大权闭合图问题，利用网络流算法求解。创建源点S和汇点T，将用户群和中转站看作图中的节点。源点向每个用户群连边，边权为该用户群带来的收益；每个中转站向汇点连边，边权为该中转站的建立成本；用户群向其依赖的中转站连边，边权为无穷大。通过求最小割（最大流），用总收益减去最小割的值，得到最大净获利。
最大权闭合图代码逐段分析
- 头文件和全局变量定义
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55010, M = (50000 * 3 + 5000) * 2 + 10, INF = 1e8;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
引入必要头文件，定义常量N（最大节点数）、M（最大边数）、INF（无穷大）。变量n为中转站数量，m为用户群数量，S为源点，T为汇点。h、e、f、ne、idx用于构建邻接表存储图的边，q、d、cur用于BFS和增广路径查找。
- 添加边函数
void add(int a, int b, int c)
{
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx ++ ;
}
在图中添加从a到b容量为c的边，同时添加反向边（容量为0）用于网络流反向增广。
- 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])
{
d[ver] = d[t] + 1;
cur[ver] = h[ver];
if (ver == T) return true;
q[ ++ tt] = ver;
}
}
}
return false;
}
使用BFS构建层次图，标记节点层次，若能到达汇点T则返回true，否则返回false。
- 增广路径查找函数
int find(int u, int limit)
{
if (u == T) return limit;
int 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])
{
int t = find(ver, min(f[i], limit - flow));
if (!t) d[ver] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
在层次图中从节点u开始，沿层次递增路径寻找增广路径，若到达汇点T则返回流量限制limit，过程中更新边的容量。
- Dinic算法函数
int dinic()
{
int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}
不断调用BFS和find函数，计算最大流并返回。
- 主函数
int main()
{
scanf("%d%d", &n, &m);
S = 0, T = n + m + 1;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ )
{
int p;
scanf("%d", &p);
add(m + i, T, p);
}
int tot = 0;
for (int i = 1; i <= m; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(S, i, c);
add(i, m + a, INF);
add(i, m + b, INF);
tot += c;
}
printf("%d\n", tot - dinic());
return 0;
}
读取中转站数量n和用户群数量m，初始化源点S和汇点T。读取每个中转站的建立成本并与汇点连边；读取每个用户群信息，源点向用户群连边，用户群向依赖的中转站连边，并累加总收益。最后用总收益减去Dinic算法求得的最大流（最小割），输出最大净获利。
最大密度子图代码实现思路
将问题转化为最大密度子图问题，通过构建网络流图求解。先计算节点的度和初始权重，然后设置源点和汇点，根据一定规则在节点与源点、汇点之间连边。通过二分答案或直接计算，利用Dinic算法求最大流，进而得到最大密度子图的密度。
最大密度子图代码逐段分析
- 头文件和全局变量定义
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010, M = (50000 + N * 2) * 2 + 10, INF = 1e8;
int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];
int dg[N], p[N];
与最大权闭合图类似，定义相关常量和变量，其中dg数组存储节点的度，p数组存储节点的权重。
- 添加边函数
void add(int a, int b, int c1, int 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）。
-
BFS、增广路径查找、Dinic算法函数
与最大权闭合图中的实现相同，用于构建层次图、查找增广路径和计算最大流。 -
主函数
int main()
{
scanf("%d%d", &n, &m);
S = 0, T = n + 1;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ ) scanf("%d", &p[i]), p[i] *= -1;
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c, c);
dg[a] += c, dg[b] += c;
}
int U = 0;
for (int i = 1; i <= n; i ++ ) U = max(U, 2 * p[i] + dg[i]);
for (int i = 1; i <= n; i ++ )
{
add(S, i, U, 0);
add(i, T, U - 2 * p[i] - dg[i], 0);
}
printf("%d\n", (U * n - dinic()) / 2);
return 0;
}
读取节点数量n和边数量m，初始化源点S和汇点T。读取节点权重并取负，读取边信息并构建图，同时更新节点的度。计算U值，根据U值在节点与源点、汇点之间连边。最后通过计算（U * n - 最大流）/ 2得到最大密度子图的密度并输出。
时间复杂度分析
最大权闭合图和最大密度子图的代码中，构建网络流图的时间复杂度为 (O(n + m))，Dinic算法的时间复杂度为 (O(n^2m))，整体时间复杂度主要由Dinic算法决定，为 (O(n^2m))。
空间复杂度分析
使用邻接表存储图，空间复杂度为 (O(m))，加上其他辅助数组，整体空间复杂度为 (O(n + m))。
