网络流与二分图
最编程
2024-07-31 20:03:48
...
定义##
- 记图 G = (V, E)
最大流问题#####
- 记每条边所能传输的最大流量为 c(e)
- 记每条边所能传输的最大流量为 f(e)
- 传输量应当满足以下限制 0 <= f(e) <= c(e)
- 对于任意除源点和汇点之外的节点应当有流入的流量等于流出的流量。
- 目标是最大化从源点发出的数据量
割#####
- 对于某一个顶点集合 S 属于 V,从 S 出发指向S的外部的那些边的集合,记为割 (S, V \ S), 这些边的容量之和称之为割的容量
最小割问题#####
- 对于给定网络, 为了保证没有从 s 到 t 的路径, 需要删去的边的容量的最小值是多少?
匹配#####
- 在 G 中两两没有公共端点的集合 M 属于 E
边覆盖#####
- 在 G 中的任意顶点都至少是 F 中某条边的端点的边的集合 F 属于 E
独立集#####
- 在 G 中两两互不相连的顶点集合 S 属于 V
顶点覆盖#####
- G中的任意边都有至少一个端点属于 S 的顶点集合 S 属于 V
性质##
最大流 = 最小割#####
- 任意一个流都小于等于任意一个割
- 构造出一个流(最大流)等于一个割
- 显然最大流等于最小割
- PS:关于这个证明我感觉下面解释的比较好。
We will assume that we are in the situation in which no augmenting path in the network has been found. Let's color in yellow, like in the figure above, every vertex that is reachable by a path that starts from the source and consists of non-full forward edges and of non-empty backward edges. Clearly the sink will be colored in blue, since there is no augmenting path from the source to the sink. Now take every edge that has a yellow starting point and a blue ending point. This edge will have the flow equal to the capacity, otherwise we could have added this edge to the path we had at that point and color the ending point in yellow. Note that if we remove these edges there will be no directed path from the source to the sink in the graph. Now consider every edge that has a blue starting point and a yellow ending point. The flow on this edge must be 0 since otherwise we could have added this edge as a backward edge on the current path and color the starting point in yellow. Thus, the value of the flow must equal the value of the cut, and since every flow is less or equal to every cut, this must be a maximum flow, and the cut is a minimum cut as well.
原文
最大匹配 = 最小顶点覆盖#####
- 记二分图 G = (U or V, E),在通过最大流求解最大匹配(设最大匹配为K)所得到的残留网络中,令 S = (从s不可到达的属于U的顶点)or(从s可以到达的属于V的顶点), 则S是G的一个最小顶点覆盖。
-
|S| = |K|
我们考虑(从s不可到达的属于U的顶点 L), 此时s向L连的边一定是满流的, 所以它一定会向V匹配一条边E(L,R), 而此时这条边的右端点(设为R,R属于V), 一定是不可到达的, 如果R可以到达, s就可以通过E的反向边到达L。
我们考虑(从s可以到达的属于V的顶点 R), 此时R向t连的边一定是满流的, 所以它一定是由V匹配的一条边E(L, R)得出的, 而此时这条边的左端点(设为L, L属于U), 一定是可以到达的(通过反向边)。
所以我们得出此时二分图匹配的边和S中的顶点一一对应, 所以|S| = |K|。 -
S覆盖了所有的边。
我们假设有的边没有被覆盖, 则它的端点分为三种情况。 -
两个端点都不属于最大匹配
把这条边加进最大匹配可以得到更优的匹配, 显然不可能。 -
两个端点都是最大匹配的端点
从残量网络的角度考虑显然这条边属于最大匹配。 -
一个端点是最大匹配的端点, 另一个端点不是
简便起见, 我们规定左端点是最大匹配的端点而右端点不是。
显然左端点属于(从s可以到达的属于U的顶点), 我们可以走右端点而走出一条交错路(增广路), 就又可以增广了,显然不可能。 -
S是最小的点覆盖。
单单覆盖最大匹配的顶点就至少需要|S|个顶点, 再小的话就有点没有被覆盖了。
对于连通图, |最大匹配| + |最小边覆盖| = |V|#####
- 考虑我们要求出一个最小边覆盖, 显然一个边要尽可能多地覆盖两个之前没有覆盖过的顶点(红色)
- 剩下的边保证一条边覆盖一个定点就好了。(蓝色)
- 证明完毕
|最大独立集| + |最小顶点覆盖| = |V|#####
由最大独立集的定义可知这些顶点两两之间没有边相连, 那最小顶点覆盖只需要盖掉剩下的顶点即可。
代码##
Dinic#####
struct Edge
{
int d, cap, rev;
Edge(int d, int cap, int rev) {
this->d = d, this->cap = cap, this->rev = rev;
}
};
vector<Edge> G[MAX_V];
int level[MAX_V], iter[MAX_V];
void add_edge(int s, int d, int cap) {
G[s].push_back(Edge(d, cap, G[d].size()));
G[d].push_back(Edge(s, 0, G[s].size() - 1));
}
void build_level(int s) {
memset(level, -1, sizeof(level));
queue<int> q;
level[s] = 0, q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (int i = 0;i < G[v].size();++i) {
Edge &e = G[v][i];
if (e.cap > 0 && level[e.d] < 0) {
level[e.d] = level[v] + 1;
q.push(e.d);
}
}
}
}
int dfs(int v, int t, int f) {
if (v == t) return f;
for (int &i = iter[v];i < G[v].size();++i) {
Edge &e = G[v][i];
if (e.cap > 0 && level[v] < level[e.d]) {
int d = dfs(e.d, t, min(f, e.cap));
if (d > 0) {
e.cap -= d, G[e.d][e.rev].cap += d;//把cap换成flow也对,想一想为什么
return d;
}
}
}
return 0;
}
int max_flow(int s, int t) {
int flow = 0;
while (true) {
build_level(s);
if (level[t] < 0) return flow;
memset(iter, 0, sizeof(iter));
int f = dfs(s, t, INF);
while (f > 0) flow += f, f = dfs(s, t, INF);
}
return flow;
}
Bipartite_matching#####
vector<int> G[MAX_V];
int V, matched[MAX_V];
bool used[MAX_V];
void add_edge(int u, int v) {
G[u].push_back(v), G[v].push_back(u);
}
int dfs(int v) {
used[v] = true;
for (int i = 0;i < G[v].size();++i) {
int u = G[v][i], w = matched[u];
if ((w < 0) || (!used[w] && dfs(w))) {
matched[u] = v, matched[v] = u;
return true;
}
}
return false;
}
int bipartite_matching() {
int result = 0;
memset(matched, -1, sizeof(matched));
for (int v = 0;v < V;++v) {
if (matched[v] < 0) {
memset(used, 0, sizeof(used));
if (dfs(v)) ++result;
}
}
return result;
}
MinCostMaxFlow#####
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <utility>
#define MAX_V (55*55*2)
#define MAX_N 55
#define OFFSET 51*50
#define INF 10000000
using namespace std;
typedef long long ll;
namespace MCMF {
struct Edge
{
int d, cap, cost;
Edge(int d, int cap, int cost)
:d(d), cap(cap), cost(cost) { }
};
vector<Edge> edges;
vector<int> G[MAX_V];
inline int rev(int x) { return x ^ 1; }
void add_edge(int s, int d, int cap, int cost) {
int k = edges.size();
edges.push_back(Edge(d, cap, cost));
edges.push_back(Edge(s, 0, -cost));
G[s].push_back(k), G[d].push_back(k + 1);
}
void init(int n) {
for (int i = 0;i <= n;++i) G[i].clear();
edges.clear();
}
int dist[MAX_V], pree[MAX_V], inq[MAX_V], prev[MAX_V];
void spfa(int s) {
queue<int> q;
memset(pree, -1, sizeof(pree));
memset(prev, -1, sizeof(prev));
memset(dist, 0x3F, sizeof(dist));
q.push(s), inq[s] = true, dist[s] = 0;
while (!q.empty()) {
int v = q.front();
q.pop(), inq[v] = false;
for (size_t i = 0;i < G[v].size();++i) {
int k = G[v][i];
Edge &e = edges[k];
if (e.cap > 0 && dist[v] + e.cost < dist[e.d]) {
dist[e.d] = dist[v] + e.cost, pree[e.d] = k, prev[e.d] = v;
if (!inq[e.d]) q.push(e.d), inq[e.d] = true;
}
}
}
}
int argu(int s, int t, int &cnt, ll &f) {
spfa(s);
if (prev[t] == -1) return 0;
int maxf = cnt;
for (int i = t;i != s;i = prev[i])
maxf = min(maxf, edges[pree[i]].cap);
for (int i = t;i != s;i = prev[i]) {
int k = pree[i];
edges[k].cap -= maxf, edges[rev(k)].cap += maxf;
f += edges[k].cost * maxf;
}
return maxf;
}
ll solve(int s, int t, int cnt) {
ll flow = 0; int flag = true;
while (cnt > 0 && flag) {
flag = argu(s, t, cnt, flow);
cnt -= flag;
}
return !cnt ? flow : -1;
}
}
int N, K, A[MAX_N][MAX_N];
inline int in(int x,int y) { return x * 50 + y; }
inline int out(int x, int y) { return x * 50 + y + OFFSET; }
int main(int argc,char *argv[]) {
scanf("%d%d", &N, &K);
for (int i = 1;i <= N;++i)
for (int j = 1;j <= N;++j) {
scanf("%d", &A[i][j]);
MCMF::add_edge(in(i, j), out(i, j), 1, -A[i][j]);
MCMF::add_edge(in(i, j), out(i, j), INF, 0);
if (i != N) add_edge(out(i, j), in(i + 1, j));
if (j != N) add_edge(out(i, j), in(i, j + 1));
}
printf("%d\n", MCMF::solve(out(1, 1), in(N, N), K));
}
引用:
二分图最大匹配的König定理及其证明
挑战程序设计竞赛(第二版)
[Poj 1459] 网络流(一) {基本概念与算法}
推荐阅读
-
使用Python实现中国邮递员问题的图与网络相关方法
-
梳理轨迹预测相关文献:探索多样性轨迹、车辆轨迹与图神经网络、潜码技术
-
二分图与网络流:基础概念、关键定理与常用算法详解
-
网络流--最大权闭合子图 *
-
ACM AtCoder AGC038F题解:两组排列(用网络流与最小割方法探讨)
-
网络流与二分图
-
实战攻略:工作流引擎深度解析 - 思维导图与具体案例" 目录概览: 1. 业务场景实战合集 2. 背景介绍:处理复杂场景 - 如请假、离职流程中的多步骤审批差异 - 详细示例:请假与离职流程的应用演示 3. 案例应用实例: - 内部企业系统(如OA)中的请假、离职流程审批 - 在内容创作工具(如PPT、海报模板)提供下载功能时,针对不同租户设置个性化审批流程 4. 技术选型与实践探讨 注:图片文件名 - "思维导图.png" 和 "请假流程.png" 无需修改。
-
理解工作流:自动化业务流程管理与Activiti实践" **简述** 工作流(Workflow)是一种利用电脑技术自动化管理业务流程的方式,让不同参与者按既定路径执行任务,确保文档、信息或任务在预设规则下顺利传递,最终达成期望的业务目标。 **核心概念** - **工作流自动化**: 计算机驱动业务流程处理与执行,如在参与者间自动传递文档和任务。 - **目标与应用**: 管理工作流程确保按时、由合适的人执行,同时允许人工介入以增强灵活性。 - **工作流框架示例**: Activiti、JBPM、OSWorkflow 和 Workflow,它们背后通常依赖数据库支持。 - **关键组件**: ProcessEngine 在 Activiti 中扮演核心角色,负责流程实例创建、数据管理和流程监控。 **相关领域** - **业务流程管理 (BPM)**: 一种系统性方法论,聚焦于构建并优化端到端卓越业务流程以提升企业业绩,在EMBA、MBA等商业课程中得到关注。 - **业务流程建模与标记语言 (BPMN)**: 用于绘制业务流程图的工具,探讨其在不同场景下的应用精确度、标准化价值以及未来发展愿景。 **辅助术语** - 流对象 (Flow Objects): BPMN 中用于描述流程中活动、决策、序列和其他元素的具体实现单元。
-
探讨网络流量中的二分图配对方法
-
理解深度学习:神经网络基础(三) - 前向传播、反向传播与计算图详解