高级网站开发工程师考试题,如何选择医疗网站建设,建筑网入口,怎样更改WordPress的密码之前那篇博客是在入门网络流时写的#xff0c;现在对网络流重新有了一定的理解。
1. 最大流
FF 增广思想
Ford–Fulkerson 增广#xff0c;核心即不断找增广路并增广。
dfs 实现
// FF brute
#include bits/stdc.h
#define int long longusing namespace std;in…之前那篇博客是在入门网络流时写的现在对网络流重新有了一定的理解。
1. 最大流
FF 增广思想
Ford–Fulkerson 增广核心即不断找增广路并增广。
dfs 实现
// FF brute
#include bits/stdc.h
#define int long longusing namespace std;int n, m, s, t, r[205][205], ans;bool vis[205];
int dfs(int u, int sum) // sum流入 u 的流量
{if(sum 0 or u t) return sum;vis[u] true;int flow 0;for(int i1; in; i){if(!vis[i] and r[u][i] 0){//找 u 到 t 路上的最小限制并增广int d dfs(i, min(sum, r[u][i]));r[u][i] - d, r[i][u] d;flow d, sum - d;}}return flow;
}signed main()
{cin n m s t;for(int i1; im; i){int u, v, w;cin u v w;r[u][v] w;}int d;while(d dfs(s, 1e9)) {memset(vis, 0, sizeof(vis));ans d;}cout ans;
}这种方法的复杂度与最大流 f f f 有关至多执行 f f f 轮 dfs时间复杂度 O ( n f ) O(nf) O(nf)。
bfs 实现 / EK
FF 增广的 bfs 实现也称 EK 算法。
// FF EK#include bits/stdc.h
#define int long longusing namespace std;int n, m, s, t, r[205][205], ans, d[205], pre[205];
queue int q;
bool bfs()
{memset(d, 0, sizeof(d)); memset(pre, 0, sizeof(pre));d[s] 1, q.push(s); while(!q.empty()){int u q.front(); q.pop();for(int i1; in; i)if(d[i] 0 and r[u][i] 0)pre[i] u, d[i] d[u] 1, q.push(i);}return d[t];
}int augment()
{int flow 1e9;for(int at; a!s; apre[a]) flow min(flow, r[pre[a]][a]);for(int at; a!s; apre[a]) r[pre[a]][a] - flow, r[a][pre[a]] flow;return flow;
}signed main()
{cin n m s t;for(int i1; im; i){int u, v, w;cin u v w;r[u][v] w;}while(bfs()) ans augment();cout ans;
}EK 算法的时间复杂度是 O ( n m 2 ) O(nm^2) O(nm2)。
证明每条边至多做 n 2 \dfrac n 2 2n 次增广路上的关键边。 OI-wiki
Dinic
通过 bfs 对图分层标记每次 dfs 只访问下一层的结点。 同时加上当前弧优化即不重复访问满流边维护第一条有必要尝试的边。
// dinic#include bits/stdc.h
#define int long longusing namespace std;struct Edge{int nxt, to, r;
}e[10005];int tot 1, head[205];
void add_edge(int u, int v, int w)
{e[tot] {head[u], v, w};head[u] tot;
}int n, m, s, t, ans, d[205], cur[205];queue int q;
bool bfs()
{memset(d, 0, sizeof(d)); d[s] 1, q.push(s); while(!q.empty()){int u q.front(); q.pop();for(int ihead[u]; i; ie[i].nxt){int v e[i].to;if(d[v] 0 and e[i].r 0)d[v] d[u] 1, q.push(v);}}return d[t];
}int dfs(int u, int sum)
{if(sum 0 or u t) return sum;int flow 0;for(int icur[u]; i; ie[i].nxt){cur[u] i;int v e[i].to;if(d[v] d[u] 1 and e[i].r 0){int d dfs(v, min(sum, e[i].r));e[i].r - d, e[i^1].r d;flow d, sum - d;}}return flow;
}signed main()
{cin n m s t;for(int i1; im; i){int u, v, w;cin u v w;add_edge(u, v, w);add_edge(v, u, 0);}while(bfs()) {for(int i1; in; i) cur[i] head[i];ans dfs(s, 1e9);}cout ans;
}
2. 二分图最大匹配 二分图对于 G ( V , E ) G(V,E) G(V,E)分成两个点集 V 1 , V 2 V1,V2 V1,V2 对于所有的 ( u , v ) ∈ E (u,v) \in E (u,v)∈E 保证 u , v u,v u,v 属于不同点集。 容易发现二分图中不存在奇环。 二分图的匹配选定一些边这些边之间没有公共点。
建网络流模型即可通过虚拟源点和虚拟汇点限制 1 1 1。
如果要输出方案可以通过 f ( u , v ) c ( u , v ) f(u,v) c(u,v) f(u,v)c(u,v)判断。如果根据残量网络需要根据反向边的残量网络判断。
#include bits/stdc.h
using namespace std;int n, m, s, t, r[105][105], ans, d[105], cur[105];
queue int q;
bool bfs()
{memset(d, 0, sizeof(d)); d[s] 1, q.push(s); while(!q.empty()){int u q.front(); q.pop();for(int i1; in2; i)if(d[i] 0 and r[u][i] 0)d[i] d[u] 1, q.push(i);}return d[t];
}int dfs(int u, int sum)
{if(sum 0 or u t) return sum;int flow 0;for(int vcur[u]; vn2; v){cur[u] v;if(d[v] d[u] 1 and r[u][v] 0){int d dfs(v, min(sum, r[u][v]));r[u][v] - d, r[v][u] d;flow d, sum - d;}}return flow;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin m n;s n1, t n2;while(1){int u, v;cin u v;if(u -1 and v -1) break;r[u][v] 1;}for(int i1; im; i) r[s][i] 1;for(int im1; in; i) r[i][t] 1;while(bfs()) {for(int i1; in2; i) cur[i] 1;ans dfs(s, 1e9);}cout ans \n;for(int u1; um; u){for(int vm1; vn; v){if(r[v][u]) cout u v \n;}} return 0;
}
3. 最大权闭合子图
分成正点和负电把不选正点看作损失每一种割对应一种方案代表不选。
答案即为正收益减去最小损失即最小割根据最小割最大流即最大流。
具体可以看我之前的博客 浅谈网络流。 A. CF1783F Double Sort II
错排建图的套路。
先只考虑一个数列记 i i i 所在位置 p i p_i pi将 i → p i i \to p_i i→pi 建边形成若干个环每次操作可以让环上少一个点因此最小操作次数为 n n n 减去环的数量。
如果从反面出发想最多能保留几个点可以不动省操作次数能保留的数量就是环的数量。
考虑两个数列对于一个环最多被省一个点。对于一个点最多被省一次。
按 i i i 所在的两个环建边跑二分图最大匹配即可。
