Hexo
0%

网络流

Posted on In ,
Symbols count in article: 5k Reading time ≈ 5 mins.

网络流

  • 有向图G(V,E)
  • 有且仅有一个顶点S，它的入度为0，称为源点
  • 有且仅有一个顶点T，它的出度为0，称为汇点
  • 每一条弧都有非负数，叫做该边的容量；
  • 称为网络流图，记为G=(V,E,C)

网络流模型例子

想要将一些水从S运到T，必须经过一些水站，连接水站的是管道，每条管道都有它的最大能容纳的水量，求S到T最多能流多少流量。

可行流

  • 每一条狐，都有$\ f[i][j] \ \le\ c[i][j]\ $；即对于每条边，流经该边的流量不得超过该边的容量(不撑爆水管)。
  • 流量平衡：除源点S和汇点T以外的所有的点vi，即流入的流量等于流出的流量，即中转点不截流量
  • 对于源点S和汇点T有：S流出的流量等于T流入的流量

增广路

增广路上的弧的流量通过一定规则的修改，可以令整个流量放大，也就是多流流量

  • 可行流中，若$\ f[i][j]\ =\ c[i][j]\ $ ,则称$<v_i,v_j>$为饱和弧，否则为非饱和弧。若$f[i][j] \ = \ 0$，则称为零流弧，否则称为非零流弧

最大流

Ford-Fulkerson增广

若图中有m条边，最大流为f，则算法的最大复杂度O(mf)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<iostream>
#include<queue>
using namespace std;
const int maxn=205;//最大结点数
const int inf=0x7fffffff;

int r[maxn][maxn]; //残留网络，初始化为原图
bool visit[maxn];//是否被访问过
int pre[maxn];//前驱子图，记录了从顶点s到终点的一条可行路径上的其它顶点的前一个顶点，从前驱子图中找到从s到t的一条完整路径
int m,n;//边数，顶点数

bool bfs(int s,int t)  //广度优先寻找一条从s到t的增广路，若找到返回true
{
    int p;
    queue<int> q;//创建一个队列的对象
    memset(pre,-1,sizeof(pre));//初始化，把数组pre中所有元素设置为-1
    memset(visit,false,sizeof(visit));
    pre[s]=s;
    visit[s]=true;
    q.push(s);//把源点放进队列里面
    while(!q.empty())//当队列不为空，继续找下一个结点
    {
        p=q.front();//取出队首
        q.pop();
        for(int i=1;i<=n;i++)
        {
            if(r[p][i]>0&&!visit[i])//如果从p出发到其他顶点，有残留容量大于0，并且没有被标记
            {
                pre[i]=p;//记录通路
                visit[i]=true;
                if(i==t) //如果找到汇点就结束
return true;
                q.push(i);//接着将该点进栈
            }
        }
    }
    return false;
}

int EK(int s,int t)//计算最大流
{
   int flow=0,d,i;
   while(bfs(s,t))//当可以找到时
   {
       d=inf;
       for(i=t;i!=s;i=pre[i])
           d=d<r[pre[i]][i]? d:r[pre[i]][i];//找到增广路径中最小流量，如果d<r[pre[i]][i],把d的值赋给d，否则把r[pre[i]][i]的值赋给d
       for(i=t;i!=s;i=pre[i])//顺藤摸瓜找回去，正向，逆向分别更改
       {
           r[pre[i]][i]-=d;//正
           r[i][pre[i]]+=d;//反
       }
       flow+=d;//
   }
   return flow;
}
int main()
{
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        int u,v,w;
        memset(r,0,sizeof(r));//
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            r[u][v]+=w;
        }
printf("最大流：");
        printf("%d\n",EK(1,n));
    }
    return 0;
}

Edmonds-Karp算法

与Ford算法的改进地方在于，每次找简单路径时都优先找最短路

图有m条边，n个节点，此时的时间复杂度为O(mmn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#define maxn 250
#define INF 0x3f3f3f3f

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 EK {
  int n, m;             // n：点数，m：边数
  vector<Edge> edges;   // edges：所有边的集合
  vector<int> G[maxn];  // G：点 x -> x 的所有边在 edges 中的下标
  int a[maxn], p[maxn];  // a：点 x -> BFS 过程中最近接近点 x 的边给它的最大流
                         // p：点 x -> BFS 过程中最近接近点 x 的边

  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));
    m = 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++) {  // 遍历以 x 作为起点的边
          Edge& e = edges[G[x][i]];
          if (!a[e.to] && e.cap > e.flow) {
            p[e.to] = G[x][i];  // G[x][i] 是最近接近点 e.to 的边
            a[e.to] =
                min(a[x], e.cap - e.flow);  // 最近接近点 e.to 的边赋给它的流
            Q.push(e.to);
          }
        }
        if (a[t]) break;  // 如果汇点接受到了流，就退出 BFS
      }
      if (!a[t])
        break;  // 如果汇点没有接受到流，说明源点和汇点不在同一个连通分量上
      for (int u = t; u != s;
           u = edges[p[u]].from) {  // 通过 u 追寻 BFS 过程中 s -> t 的路径
        edges[p[u]].flow += a[t];      // 增加路径上边的 flow 值
        edges[p[u] ^ 1].flow -= a[t];  // 减小反向路径的 flow 值
      }
      flow += a[t];
    }
    return flow;
  }
};

Dinic算法

图有m条边，n个点，此时的时间复杂度为O(mnn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
const long long inf=2005020600;
int n,m,s,t,u,v;
long long w,ans,dis[520010];
int tot=1,now[520010],head[520010]; 

struct node {
	int to,net;
	long long val;
} e[520010];

inline void add(int u,int v,long long w) {
	e[++tot].to=v;
	e[tot].val=w;
	e[tot].net=head[u];
	head[u]=tot;
	
	e[++tot].to=u;
	e[tot].val=0;
	e[tot].net=head[v];
	head[v]=tot;
}

inline int bfs() {  //在惨量网络中构造分层图 
	for(register int i=1;i<=n;i++) dis[i]=inf;
	queue<int> q;
	q.push(s);
	dis[s]=0;
	now[s]=head[s];
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		for(register int i=head[x];i;i=e[i].net) {
			int v=e[i].to;
			if(e[i].val>0&&dis[v]==inf) {
				q.push(v);
				now[v]=head[v];
				dis[v]=dis[x]+1;
				if(v==t) return 1;
			}
		}
	}
	return 0;
}

inline int dfs(int x,long long sum) {  //sum是整条增广路对最大流的贡献
	if(x==t) return sum;
	long long k,res=0;  //k是当前最小的剩余容量 
	for(register int i=now[x];i&&sum;i=e[i].net) {
		now[x]=i;  //当前弧优化 
		int v=e[i].to;
		if(e[i].val>0&&(dis[v]==dis[x]+1)) {
			k=dfs(v,min(sum,e[i].val));
			if(k==0) dis[v]=inf;  //剪枝，去掉增广完毕的点 
			e[i].val-=k;
			e[i^1].val+=k;
			res+=k;  //res表示经过该点的所有流量和（相当于流出的总量） 
			sum-=k;  //sum表示经过该点的剩余流量 
		}
	}
	return res;
}

int main() {
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(register int i=1;i<=m;i++) {
		scanf("%d%d%lld",&u,&v,&w);
		add(u,v,w);
	}
	while(bfs()) {
		ans+=dfs(s,inf);  //流量守恒（流入=流出） 
	}
	printf("%lld",ans);
	return 0;
}