HihoCoder上网络流算法题目建模总结

2024-08-26 08:32
文章标签 算法 总结 题目 网络 建模 hihocoder

本文主要是介绍HihoCoder上网络流算法题目建模总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

经过了几天的学习和做题，我利用刘汝佳书上的网络流算法模板完成了HihoCoder上的几个网络流算法，HihoCoder可能还会继续更新网络流算法，所以我也会接着总结。

这个主要是对网络流算法的建模做分析和理解，不具体分析网络流算法，网络流算法会单独总结。

网络流一·Ford-Fulkerson算法

题目连接

本题没有建模，就是标准的网络最大流求解，将图建完后直接应用最大流算法即可解决。但在此记录几点注意的地方：

  • 所谓的“残留网络”就是为了让程序在遍历时可以会推所添加的记录流量差的反向边。比如 a–>b 容量为10，流量为3，其意义为从a到b已经走了3个流量，还有7个流量可以走过去，3个流量可以再退回来。

  • 增广路径就是找从 s 到 t 的能通过的路径，所谓能通过就是还存在未满流的边可以再走一些流量。这类增广路径算法的思想就是不断地在“残留网络”上找“增广路径”，然后修改残留网络上的流量，直到不通为止。

代码如下，为刘汝佳书《算法竞赛入门经典》中一个模板：

const int maxn = 505;
const int INF = 0x7fffffff;struct Edge {int from, to, cap, flow;Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};struct EdmondsKarp {int n, m;vector<Edge> edges;vector<int> G[maxn];int a[maxn];int p[maxn];void init(int n) {for (int i = 0; i < n; ++i) G[i].clear();edges.clear();}void AddEdge(int from, int to, int cap) {edges.push_back(Edge(from, to, cap, 0));edges.push_back(Edge(to, from, 0, 0));  // reverse edgem = edges.size();G[from].push_back(m - 2);G[to].push_back(m - 1);}int Maxflow(int s, int t) {int flow = 0;for (;;) {memset(a, 0, sizeof(a));queue<int> Q;Q.push(s);a[s] = INF;while (!Q.empty()) {int x = Q.front(); Q.pop();for (int i = 0; i < G[x].size(); ++i) {Edge &e = edges[G[x][i]];if (!a[e.to] && e.cap > e.flow) {p[e.to] = G[x][i];a[e.to] = min(a[x], e.cap - e.flow);Q.push(e.to);}}if (a[t]) break;}if (!a[t]) break;for (int u = t; u != s; u = edges[p[u]].from) {edges[p[u]].flow += a[t];edges[p[u] ^ 1].flow -= a[t];}flow += a[t];}return flow;}
};int main()
{
#ifdef LOCALfreopen("input.txt", "r", stdin);// freopen("sorted.txt", "w", stdout);
#endifint N, M, u, v, c;cin >> N >> M;EdmondsKarp ek;// construct the graphek.init(N);for (int i = 0; i < M; ++i) {cin >> u >> v >> c;ek.AddEdge(u, v, c);}cout << ek.Maxflow(1, N) << endl;return 0;}

网络流二·最大流最小割定理

题目连接

这部分主要是证明最小割等于最大流，证明详细步骤见上面题目，这里记录下主要步骤：

  • f(S, T) 等于从 s 出来的流，等于当前的网络流量 f。f(S, T) 表示割 (S, T)的净流量。

  • 对于网络的任何一个流，一定小于等于任何一个割的容量（f(S, T) <= C(S, T)

对于一个网络 G=(V, E)，有源点 s 汇点 t，以下三个等价：
1、f 是图 G 的最大流
2、残留网络不存在增广路
3、对于G的一个割(S, T)，此时 f = C(S, T)
证明：
1=>2：假设 f 是图 G 的最大流，如果残留网络存在增广路 p，流量为 fp，那么有流 f’ = f + fp > f ，与 f 是最大流矛盾。
2=>3：对于任意的 u S v T，有 f(u, v) = c(u, v)，即

∑f(u,v)=∑c(u,v)=f(S,T)=C(S,T)=f

这样，找不到增广路的时候求得的一定是最大流，最大流等于最小割。

另外，本题要求求出最小割集合 S，在割 (S, T) 中，计算出的残留网络从 s 开始遍历，所能遍历到的点即为 S 集合，因为求得的最小割就是最大流，最大流中残留网络不存在增广路径，也就是说从 s 没法走到 t，故从 s 开始遍历，所得到的点的集合就是 S。

const int maxn = 505;
const int INF = 0x7FFFFFFF;struct Edge {int from, to, cap, flow;Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};bool used[maxn];
std::vector<int> rst;struct EdmondsKarp {int n, m;vector<Edge> edges;vector<int> G[maxn];int a[maxn];int p[maxn];void init(int n) {for (int i = 0; i < n; ++i) G[i].clear();edges.clear();}void AddEdge(int from, int to, int cap) {edges.push_back(Edge(from, to, cap, 0));edges.push_back(Edge(to, from, 0, 0));  // reverse edgem = edges.size();G[from].push_back(m - 2);G[to].push_back(m - 1);}int Maxflow(int s, int t) {int flow = 0;for (;;) {memset(a, 0, sizeof(a));queue<int> Q;Q.push(s);a[s] = INF;while (!Q.empty()) {int x = Q.front(); Q.pop();for (int i = 0; i < G[x].size(); ++i) {Edge &e = edges[G[x][i]];if (!a[e.to] && e.cap > e.flow) {p[e.to] = G[x][i];a[e.to] = min(a[x], e.cap - e.flow);Q.push(e.to);}}if (a[t]) break;}if (!a[t]) break;for (int u = t; u != s; u = edges[p[u]].from) {edges[p[u]].flow += a[t];edges[p[u] ^ 1].flow -= a[t];}flow += a[t];}   return flow;}   void GetMinCutSetS(int s) {rst.push_back(s); used[s] = true;for (int i = 0; i < G[s].size(); ++i) {Edge &e = edges[G[s][i]];if (!used[e.to] && e.flow != e.cap) {GetMinCutSetS(e.to);}}}
};int main(int argc, char** argv) {
#ifdef LOCALfreopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#endif// 2 <= N <= 500, 1 <= M <= 20000int N, M; cin >> N >> M;EdmondsKarp ek;ek.init(N);// construct the graphint u, v, c;for (int i = 0; i < M; ++i) {cin >> u >> v >> c;ek.AddEdge(u, v, c);}int flow = ek.Maxflow(1, N);ek.GetMinCutSetS(1);std::cout << flow << " " << rst.size() << std::endl;for (int i = 0; i < rst.size() - 1; ++i) {cout << rst[i] << " ";}std::cout << rst[rst.size() - 1] << std::endl;return 0;
}

说明：代码中的 GetMinCutSetS 就是一个 DFS 方法，从一个点开始遍历得到最终的 S 集合，没什么难的。结果保存在一个 vector 中。

网络流三·二分图多重匹配

题目连接

二分图的多重匹配，其实质就是需要规定 X 集中的点可以使用多少次，Y 中的点可以重用多少次，如果 X 中的某个点的流量使用完毕，则这条边满流，则不可再次使用。从源点 s 指向 X 集中的边的容量则规定了这个点能用多少次！Y 集中的指向汇点 t 的边的容量也是如此含义。所以，如果 Y 集中的容量没有用光，则说明当前的流（匹配）还没有达到所期望的要求。
这题使用了CheckMaxMatch 用来判断指向汇点的边是否满流。

const int maxn = 1005;
const int INF = 0x7FFFFFFF;struct Edge {int from, to, cap, flow;Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};// 求最小割所用到的两个
// 求最小割点的思路为在原来求最大流的残留网络上从 s 点开始 DFS，所有能遍历到的点都是 S 集合里面的，
// 剩余没有遍历到的点就是 T 集合里的点。
// bool used[maxn];
// std::vector<int> rst;
struct EdmondsKarp {int n, m;vector<Edge> edges;vector<int> G[maxn];int a[maxn];int p[maxn];void init(int n) {for (int i = 0; i < n; ++i) G[i].clear();edges.clear();}void AddEdge(int from, int to, int cap) {edges.push_back(Edge(from, to, cap, 0));edges.push_back(Edge(to, from, 0, 0));  // reverse edgem = edges.size();G[from].push_back(m - 2);G[to].push_back(m - 1);}int Maxflow(int s, int t) {int flow = 0;for (;;) {memset(a, 0, sizeof(a));queue<int> Q;Q.push(s);a[s] = INF;while (!Q.empty()) {int x = Q.front(); Q.pop();for (int i = 0; i < G[x].size(); ++i) {Edge &e = edges[G[x][i]];if (!a[e.to] && e.cap > e.flow) {p[e.to] = G[x][i];a[e.to] = min(a[x], e.cap - e.flow);Q.push(e.to);}}if (a[t]) break;}if (!a[t]) break;for (int u = t; u != s; u = edges[p[u]].from) {edges[p[u]].flow += a[t];edges[p[u] ^ 1].flow -= a[t];}flow += a[t];}return flow;}bool CheckMaxMatch(int N, int M) {for (int i = 1; i <= M; ++i) {for (int j = 0; j < G[N + i].size(); ++j) {Edge &e = edges[G[N + i][j]];if (e.flow != e.cap && e.flow > 0) { return false; }}}return true;}/* // 遍历求网络的最小割中的 S 集合点，结果储存在上面的 vector<int> rst 中；void GetMinCutSetS(int s) {rst.push_back(s); used[s] = true;for (int i = 0; i < G[s].size(); ++i) {Edge &e = edges[G[s][i]];if (!used[e.to] && e.flow != e.cap) {GetMinCutSetS(e.to);}}}*/
};int main(int argc, char** argv) {
#ifdef LOCALfreopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#endifint T; cin >> T;while (T--) {int N, M; cin >> N >> M;EdmondsKarp ek;ek.init(N + M + 2);int m[maxn + 5], a[maxn + 5], b[maxn + 5];for (int i = 0; i < M; ++i) cin >> m[i];for (int i = 0; i < N; ++i) {cin >> a[i] >> b[i];int tmprecv;for (int j = 0; j < b[i]; ++j) {cin >> tmprecv;// X -> Yek.AddEdge(i + 1, tmprecv + N, 1);}}for (int i = 1; i <= N; ++i) {ek.AddEdge(0, i, a[i - 1]);}for (int i = 1; i <= M; ++i) {ek.AddEdge(N + i, N + M + 1, m[i - 1]);}ek.Maxflow(0, N + M + 1);cout << (ek.CheckMaxMatch(N, M) ? "Yes" : "No") << endl;}return 0;
}

网络流四·最小路径覆盖

题目连接

建图的方法为：
1、添加源点 s 和汇点 t。
2、拆点，将每个点拆成两个点，比如 a 拆成 a1, a2，b 拆成 b1, b2。
3、从源点向 X 集合中每个点添加一条容量为 1 的有向边。
4、从 Y 集合向汇点中每个点添加一条容量为 1 的有向边。
5、如果 a -> b 有边，则从 a1 向 b2 添加一条容量为 1 的有向边。

最小路径覆盖就是总点数 N - 最小割。证明在我学会之前暂时不写。

推荐去看《计算机算法设计与分析》中的网络流 24 题中的魔术球问题，这是一道很隐晦的利用网络流的最小路径覆盖问题，很经典。

const int maxn = 1005;
const int INF = 0x7FFFFFFF;struct Edge {int from, to, cap, flow;Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};
// 求最小割所用到的两个
// 求最小割点的思路为在原来求最大流的残留网络上从 s 点开始 DFS，所有能遍历到的点都是 S 集合里面的，
// 剩余没有遍历到的点就是 T 集合里的点。
// bool used[maxn];
// std::vector<int> rst;
struct EdmondsKarp {int n, m;vector<Edge> edges;vector<int> G[maxn];int a[maxn];int p[maxn];void init(int n) {for (int i = 0; i < n; ++i) G[i].clear();edges.clear();}void AddEdge(int from, int to, int cap) {edges.push_back(Edge(from, to, cap, 0));edges.push_back(Edge(to, from, 0, 0));  // reverse edgem = edges.size();G[from].push_back(m - 2);G[to].push_back(m - 1);}int Maxflow(int s, int t) {int flow = 0;for (;;) {memset(a, 0, sizeof(a));queue<int> Q;Q.push(s);a[s] = INF;while (!Q.empty()) {int x = Q.front(); Q.pop();for (int i = 0; i < G[x].size(); ++i) {Edge &e = edges[G[x][i]];if (!a[e.to] && e.cap > e.flow) {p[e.to] = G[x][i];a[e.to] = min(a[x], e.cap - e.flow);Q.push(e.to);}}if (a[t]) break;}if (!a[t]) break;for (int u = t; u != s; u = edges[p[u]].from) {edges[p[u]].flow += a[t];edges[p[u] ^ 1].flow -= a[t];}flow += a[t];}return flow;}
};
int main(int argc, char** argv) {
#ifdef LOCALfreopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#endifint N, M; cin >> N >> M;EdmondsKarp edk;edk.init(N + N);int u, v;for (int i = 1; i <= M; ++i) {cin >> u >> v;edk.AddEdge(u, v + N, 1);}for (int i = 1; i <= N; ++i) {edk.AddEdge(0, i, 1);edk.AddEdge(N + i, N + N + 1, 1);}cout << N - edk.Maxflow(0, N + N + 1) << endl;return 0;
}

网络流五·最大权闭合子图

题目连接

最大权闭合子图：目前就我的理解是用来建模求解一些有“收入”以及“支出”并且求最后最大的收益类问题的。建模方法如下：

1、添加源点 s 和汇点 t 。
2、从源点 s 向 X 集合中每个点连一条容量为该点“收入”的有向边。
3、从 Y 集合中每个点向汇点 t 连一条容量为该点“支出”的有向边。
4、若 X 和 Y 集合中的点有依赖关系，则从 X 集合向 Y 集合每个关系添加一条容量为无限大的有向边。

最终的结果为所有收入之和 - 最小割。

const int maxn = 1005;
const int INF = 0x7FFFFFFF;struct Edge {int from, to, cap, flow;Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};
// 求最小割所用到的两个
// 求最小割点的思路为在原来求最大流的残留网络上从 s 点开始 DFS，所有能遍历到的点都是 S 集合里面的，
// 剩余没有遍历到的点就是 T 集合里的点。
// bool used[maxn];
// std::vector<int> rst;
struct EdmondsKarp {int n, m;vector<Edge> edges;vector<int> G[maxn];int a[maxn];int p[maxn];void init(int n) {for (int i = 0; i < n; ++i) G[i].clear();edges.clear();}void AddEdge(int from, int to, int cap) {edges.push_back(Edge(from, to, cap, 0));edges.push_back(Edge(to, from, 0, 0));  // reverse edgem = edges.size();G[from].push_back(m - 2);G[to].push_back(m - 1);}int Maxflow(int s, int t) {int flow = 0;for (;;) {memset(a, 0, sizeof(a));queue<int> Q;Q.push(s);a[s] = INF;while (!Q.empty()) {int x = Q.front(); Q.pop();for (int i = 0; i < G[x].size(); ++i) {Edge &e = edges[G[x][i]];if (!a[e.to] && e.cap > e.flow) {p[e.to] = G[x][i];a[e.to] = min(a[x], e.cap - e.flow);Q.push(e.to);}}if (a[t]) break;}if (!a[t]) break;for (int u = t; u != s; u = edges[p[u]].from) {edges[p[u]].flow += a[t];edges[p[u] ^ 1].flow -= a[t];}   flow += a[t];}return flow;}bool CheckMaxMatch(int N, int M) {for (int i = 1; i <= M; ++i) {for (int j = 0; j < G[N + i].size(); ++j) {Edge &e = edges[G[N + i][j]];if (e.flow != e.cap && e.flow > 0) { return false; }}           }return true;}/* // 遍历求网络的最小割中的 S 集合点，结果储存在上面的 vector<int> rst 中；void GetMinCutSetS(int s) {rst.push_back(s); used[s] = true;for (int i = 0; i < G[s].size(); ++i) {Edge &e = edges[G[s][i]];if (!used[e.to] && e.flow != e.cap) {GetMinCutSetS(e.to);}}}*/
};
int main(int argc, char** argv) {
#ifdef LOCALfreopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#endifint N, M; cin >> N >> M;int b[maxn], sum = 0;EdmondsKarp ek;ek.init(N + M + 2);// 第i个数表示邀请编号为i的学生需要花费的活跃值b[i]for (int i = 1; i <= M; ++i) cin >> b[i];for (int i = 1; i <= N; ++i) {int a, k, recvtmp; cin >> a >> k;sum += a;ek.AddEdge(0, i, a);for (int j = 1; j <= k; ++j) {cin >> recvtmp;ek.AddEdge(i, recvtmp + N, INF);}}for (int i = 1; i <= M; ++i) {ek.AddEdge(i + N, N + M + 1, b[i]);}cout << sum - ek.Maxflow(0, N + M + 1) << endl;return 0;
}

这篇关于HihoCoder上网络流算法题目建模总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1108064。

相关文章

Android数据库Room的实际使用过程总结

Android数据库Room的实际使用过程总结

《Android数据库Room的实际使用过程总结》这篇文章主要给大家介绍了关于Android数据库Room的实际使用过程,详细介绍了如何创建实体类、数据访问对象（DAO）和数据库抽象类,需要的朋友可以... 目录前言一、Room的基本使用1.项目配置2.创建实体类（Entity）3.创建数据访问对象（DAO
阅读更多...
Java向kettle8.0传递参数的方式总结

Java向kettle8.0传递参数的方式总结

《Java向kettle8.0传递参数的方式总结》介绍了如何在Kettle中传递参数到转换和作业中,包括设置全局properties、使用TransMeta和JobMeta的parameterValu... 目录1.传递参数到转换中2.传递参数到作业中总结1.传递参数到转换中1.1. 通过设置Trans的
阅读更多...
C# Task Cancellation使用总结

C# Task Cancellation使用总结

《C#TaskCancellation使用总结》本文主要介绍了在使用CancellationTokenSource取消任务时的行为,以及如何使用Task的ContinueWith方法来处理任务的延... 目录C# Task Cancellation总结1、调用cancellationTokenSource.
阅读更多...
HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2