网络流
给一个有向图，每条边有一个权值：流量，即从u到v的流量不能超过这个值，然后给两个点：源点和汇点，求从源点到汇点的最大总流量。
解决最大流问题的算法有(时间复杂度从劣到优)：FF算法，EK算法，DINIC算法，HLPP算法..
观察了几个算法，每个算法都有一个步骤，找到一条路之后，把它们的流量反向，比如u到v有x的流量，那么从v到u就有-x的流量，对于非源点和非汇点的每个点，它们自身的流量和为0，满足能量守恒定理。
EK算法
时间复杂度O(V^2E)
BFS做法，每次使用BFS找到一条路，直到找不到为止。
c用来存图，表示每条边的最大流量，f表示已经流过的流量，二者相减为剩余流量，剩余流量大于0表示这条边还可以通流。vis[i]表示源点到i的最大流量。
HDU3549 Flow Problem
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
int n, m, x, y, z;
int c[16][16], f[16][16], vis[16], pre[16], sum;
void EK(){
queue<int> q;
while (1){
memset (vis, 0, sizeof vis);
memset (pre, 0, sizeof pre);
q.push(1); vis[1] = 9999999;
while (!q.empty()){
int x = q.front(); q.pop();
for (int i=1; i<=n; i++) if (!vis[i] && f[x][i]<c[x][i]){
vis[i] = min(vis[x], c[x][i]-f[x][i]);
pre[i] = x;
q.push(i);
}
}
if (!vis[n]) break;
int tmp = n;
sum += vis[n];
while (pre[tmp]){
f[pre[tmp]][tmp] += vis[n];
f[tmp][pre[tmp]] -= vis[n];
tmp = pre[tmp];
}
}
}
int main(){
int cas = 0;
scanf ("%d", &n);
while (~scanf ("%d %d", &n, &m)){
memset (c, 0, sizeof c);
memset (f, 0, sizeof f);
sum = 0;
for (int i=1; i<=m; i++){
scanf ("%d %d %d", &x, &y, &z);
c[x][y] += z;
}
EK();
printf ("Case %d: %d\n", ++cas, sum);
}
return 0;
}DINIC算法
时间复杂度O(VE)
在EK算法中，每寻找一条路就要BFS一次，是在太慢了，DINIC算法是对EK算法的一个大优化。
BFS+DFS来解决问题。
每次寻找路前，先用BFS跑一遍，判断是否还存在路到达汇点，并给每个点标层，然后DFS寻找流路。DFS函数有三个参数：源点s，汇点t，可以分发的流量flow，即把这flow的流量分给s指向的几个点，最后剩下rest流量，那么就有flow-rest的流量流到了汇点。
存图是用vector存，存边用数组，具体见代码，每条边都有对应的反向，第i条边的反向是第i^1条边，边的下标必须从0开始(因为0和1对应，在^运算符下)。
还要注意的是这里面是有多重边的，而且每条边都会建立反向，EK算法里的邻接矩阵是把多重边合并，因为是用矩阵存的图，那样的话对于点数较小的图就很快的，但当点数较多时，边数就相对来说少很多了(相对V^2，完全图)。
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
int n, m, x, y, z, cnt;
struct edge{
int from, to, c, f;
edge(int u, int v, int cap, int flow): from(u), to(v), c(cap), f(flow){}
};
int depth[30], cur[30];
vector<edge> e;
vector<int> G[30];
inline bool BFS(int s, int t){
memset (depth, 0, sizeof depth);
queue<int> q;
q.push(s); depth[s] = 1;
while (!q.empty()){
s = q.front(); q.pop();
for (int i=0; i<G[s].size(); i++){
edge &tmp = e[G[s][i]];
if (tmp.c>tmp.f && !depth[tmp.to]){ //只考虑有剩余流量的边
depth[tmp.to] = depth[s] + 1;
q.push(tmp.to);
}
}
}
return depth[t];
}
inline int DFS(int s, int flow, int t){
if (s==t || flow<=0) return flow;
int rest = flow;
for (int &i=cur[s]; i<G[s].size(); i++) if (e[G[s][i]].c>e[G[s][i]].f && depth[e[G[s][i]].to]==depth[s]+1){ //枚举s指向的每个点，若连接他俩的边还有剩余流量，那么就可以考虑 弧优化
int tmp = DFS(e[G[s][i]].to, min(rest, e[G[s][i]].c-e[G[s][i]].f), t); //tmp暂存可以从这条边流出去的流量
if (tmp<=0){ //剪枝优化
depth[e[G[s][i]].to] = 0;
continue;
}
rest -= tmp; //可以流出tmp，那么rest就减去tmp，对应的边和反向边就分别加减tmp
e[G[s][i]].f += tmp;
e[G[s][i]^1].f -= tmp;
if (rest==0) break; //很重要的一步。。。
}
return flow - rest;
}
int DINIC(int s, int t){
int ans = 0;
while (BFS(s, t)){
ans += DFS(s, 999999999, t);
for (int i=1; i<=n; i++) cur[i] = 0;
}
return ans;
}
inline void add(int from, int to, int cap){
e.push_back(edge(from, to, cap, 0));
e.push_back(edge(to, from, 0, 0));
cnt += 2;
G[from].push_back(cnt-2);
G[to].push_back(cnt-1);
return;
}
int main(){
scanf ("%d", &x);
int cas = 0;
while (~scanf ("%d %d", &n, &m)){
e.clear();
for (int i=1; i<=n; i++) G[i].clear();
cnt = 0;
for (int i=1; i<=m; i++){
scanf ("%d %d %d", &x, &y, &z);
add(x, y, z);
}
printf ("Case %d: %d\n", ++cas, DINIC(1, n));
}
return 0;
}
0 条评论