本文主要是介绍2324. 生活的艰辛（网络流，最小割，最大密度子图）#困难，重点难点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
活动 - AcWing
约翰是一家公司的 CEO。
公司的股东决定让他的儿子斯科特成为公司的经理。
约翰十分担心，儿子会因为在经理岗位上表现优异而威胁到他 CEO 的位置。
因此，他决定精心挑选儿子要管理的团队人员，让儿子知道社会的险恶。
已知公司中一共有 n 名员工，员工之间共有 m 对两两矛盾关系。
如果将一对有矛盾的员工安排在同一个团队，那么团队的管理难度就会增大。
一个团队的管理难度系数等于团队中的矛盾关系对数除以团队总人数。
团队的管理难度系数越大，团队就越难管理。
约翰希望给儿子安排的团队的管理难度系数尽可能大。
请帮帮他。
以上图为例，管理难度系数最大的团队由 1,2,4,5 号员工组成，他们 4 人中共有 5 对矛盾关系，所以管理难度系数为 54。
如果我们将 3 号员工也加入到团队之中，那么管理难度系数就会降至 65。
输入格式
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 ai和 bi，表示员工 ai 和 bi 之间存在矛盾。
所有员工编号从 1 到 n。
每个矛盾对最多在输入中出现一次，且介绍矛盾对时，员工介绍顺序是随意的。
输出格式
首先输出一个整数 k，表示安排给斯科特的团队人员数量。
接下来 k 行，以升序输出团队每个成员的编号，每行一个。
如果答案不唯一，则输出任意一种即可。
注意：至少要选择一名员工。
数据范围
1≤n≤100,
0≤m≤1000
1≤k≤n
输入样例1：
5 6
1 5
5 4
4 2
2 5
1 2
3 1
输出样例1：
4
1
2
4
5
输入样例2：
4 0
输出样例2：
1
1
提示
注意样例 22 中，任意团队的管理困难系数都是 00，这种情况输出任意非空方案即可。
解析：
最大密度子图详细证明请参考讲义（作者小小_88）:最大密度子图的相关概念 - AcWing
关于最小割得更详细了解请阅读胡伯涛的论文：《最小割模型在信息学竞赛中的应用 》： https://www.studocu.com/row/document/changsha-university-of-science-and-technology/computer-algorithm/7%E8%83%A1%E4%BC%AF%E6%B6%9B%E6%9C%80%E5%B0%8F%E5%89%B2%E6%A8%A1%E5%9E%8B%E5%9C%A8%E4%BF%A1%E6%81%AF%E5%AD%A6%E7%AB%9E%E8%B5%9B%E4%B8%AD%E7%9A%84%E5%BA%94%E7%94%A8-changsha-university-of-science-and-technology/26399377
本题就是密度子图的一个应用，给我们 n 个点，m 条边，让我们求最大密度子图，本题需要输出方案，由于已经证明过密度子图和割一一对应，且 V′=S−{s} 所以只要找出任何一个割，再把源点删掉，剩下的点集就是一个合法方案。怎么找出一个割呢，从源点出发沿着容量 >0 的边走，凡是走得到的点都属于 S，反之属于 T。
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e2 + 10, M = (1e3 + N * 2) * 2, INF = 0x3f3f3f3f;
int n, m, S, T;
int h[N], e[M], ne[M], idx;
double f[M];
int q[N], d[N], cur[N];
int ans;
bool st[N];
int dg[N];
struct egde {int a, b;
}edges[M];void add(int a, int b, double d1, double d2) {e[idx] = b, f[idx] = d1, ne[idx] = h[a], h[a] = idx++;e[idx] = a, f[idx] = d2, ne[idx] = h[b], h[b] = idx++;
}void build(double g) {memset(h, -1, sizeof h);idx = 0;for (int i = 1; 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 + 2 * g - dg[i], 0);}
}double find(int u, double limit) {if (u == T)return limit;double flow = 0;for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {int j = e[i];cur[u] = i;if (d[j] == d[u] + 1 && f[i] > 0) {double t = find(j, min(f[i], limit - flow));if (t <= 0)d[j] = -1;f[i] -= t, f[i ^ 1] += t, flow += t;}}return flow;
}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 != -1; i = ne[i]) {int j = e[i];if (d[j] == -1 && f[i] > 0) {d[j] = d[t] + 1;cur[j] = h[j];if (j == T)return 1;q[++tt] = j;}}}return 0;
}double dinic(double mid) {build(mid);double ret = 0, flow;while (bfs())while (flow = find(S, INF))ret += flow;return ret;
}void dfs(int u) {st[u] = 1;if (u != S)ans++;for (int i = h[u]; i != -1; i = ne[i]) {int j = e[i];if (!st[j] && f[i] > 0)dfs(j);}
}int main() {cin >> n >> m;S = 0, T = n + 1;for (int i = 1; i <= m; i++) {scanf("%d%d", &edges[i].a, &edges[i].b);dg[edges[i].a]++, dg[edges[i].b]++;}double l = 0, r = m;while (r - l > 1e-8) {double mid = (r + l) / 2;double t = dinic(mid);if (n * m - t > 0)l = mid;else r = mid;}dinic(l);dfs(S);if (!ans)cout << 1 << endl << 1 << endl;else {cout << ans << endl;for (int i = 1; i <= n; i++) {if (st[i]) printf("%d\n", i);}}return 0;
}
这篇关于2324. 生活的艰辛（网络流，最小割，最大密度子图）#困难，重点难点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
