目录

网络流

最大流

EdmondsKarp

bfs找路,途中记录前驱节点

让后从汇点遍历到起点,找到最小flow

再次遍历,更新沿途边

累加答案,继续bfs

 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
#define mem(x,y) memset(x,y,sizeof(x))
#define SIZE 1005
const int INF=0x3f3f3f3f;
int G[SIZE][SIZE],pre[SIZE];
bool vst[SIZE];
bool bfs(int s,int t){
    queue<int> que;
    mem(vst,0);
    mem(pre,-1);
    pre[s]=s;
    vst[s]=true;
    que.push(s);
    while (!que.empty()) {
        int u=que.front();que.pop();
        for(int i=s;i<=t;++i){//遍历所有点
            if(G[u][i]&&!vst[i]){
                pre[i]=u;
                vst[i]=true;
                if(i==t)return true;
                que.push(i);
            }
        }
    }
    return false;
}
int EK(int s,int t){
    int ans=0;
    while (bfs(s,t)) {
        int minflow=INF;
        for(int i=t;i!=s;i=pre[i]){
            minflow=min(minflow,G[pre[i]][i]);
        }
        for(int i=t;i!=s;i=pre[i]){
            G[pre[i]][i]-=minflow;
            G[i][pre[i]]+=minflow; // 一定记得反向边
        }
        ans+=minflow;
    }
    return ans;
}

dinic

多路增广+当前弧优化

建图时候建反向边(前向星边id从0开始,这样edge[i^1]就是反边)

首先bfs分层,维护每个点到汇点的距离(每个边距离都看做1)

然后对分过层的图dfs,每找到一条通路,沿途边边权减去流量,反边加上流量,反复找直到没有

再次bfs直到没有

for(int &i=curedge[u];i!=-1;i=edge[i].nxt)

这句当前弧优化可能看不懂,代码中有详细注释

head[] edge[] 是链式前向星存图

curedge[] 当前弧优化使用

 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
#include <queue>
#include <string.h>
#define mem(x,y) memset(x,y,sizeof(x))
#define SIZE 1000
struct node{
    int v,nxt,w;//指向那个点 下条边id 权值
}edge[SIZE*2];
int head[SIZE],curedge[SIZE],dis[SIZE],ecnt,s,t;
inline void init(){
    ecnt=0;//从偶数开始都行
    mem(head,-1);
}
inline void addedge(int u,int v,int w){
    edge[ecnt].v=v;
    edge[ecnt].w=w;
    edge[ecnt].nxt=head[u];
    head[u]=ecnt;
    ecnt++;
	swap(u,v);//添加反边
	edge[ecnt].v=v;
    edge[ecnt].w=0;
    edge[ecnt].nxt=head[u];
    head[u]=ecnt;
    ecnt++;
}
bool bfs(){
    mem(dis,-1);//不能少
    dis[t]=0;//s是起点,t是终点,分层
    queue<int> que;
    que.push(t);
    while(!que.empty()){
        int u=que.front();que.pop();
        for(int i=head[u];i!=-1;i=edge[i].nxt){
            if(dis[edge[i].v]==-1&&edge[i^1].w>0){
                dis[edge[i].v]=dis[u]+1;
                que.push(edge[i].v);
            }
        }
    }
    return dis[s]!=-1;//没有办法从s到t返回false
}
int dfs(int u,int v,int flow){
    if(u==t)return flow;
    int delta=flow;//表示前面输送过来的流量有多少被挡住了,初始化为所有
    for(int &i=curedge[u];i!=-1;i=edge[i].nxt){
		//当前弧优化,& 引用是重点
        if(dis[u]==dis[edge[i].v]+1&&edge[i].w>0){
            int d=dfs(edge[i].v,v,min(delta,edge[i].w));
            edge[i].w-=d;edge[i^1].w+=d;
            delta-=d;//可以放行d的流量,被挡住的流量变少了
            if(delta==0)break;//这句对当前弧优化很重要,这时进来的流量全都放行了,那么当前这条路可能刚好被填满,也可能还有宽裕(如果delta!=0,说明这条路肯定占满了)
			//因为可能有宽裕,所以这条路以后还要走,这时候break;curedge[u]=i,前面的路因为都满了,所以直接舍去,下次到这个点直接从第i个边开始,这就是当前弧优化。
        }
    }
    return flow-delta;//送进来的 - 挡住的 = 有效流量
}
int dinic(){
    int ans=0;
    while (bfs()) {//分层(计算距离)
        for(int i=s;i<=t;i++)//每bfs一次,层次就刷新,所以也要重置当前弧
            curedge[i]=head[i];
        ans+=dfs(s,t,INF);//从点1到点n最大流,输入流量无穷大
    }
    return ans;
}

费用流

spfa

求最小费用最大流

建边时候反边cost是原来的负数

用spfa求出一条s到t的最短路,途中

pre[]数组记录当前点是从哪个边过来的(放了一个边id)

然后通过pre[]从t一直遍历到s,找到途中最小流量Min

再遍历一次,更新途中边的容量,更新答案

再次spfa直到没有通路

 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
#include <queue>
#include <string.h>
#define mem(x,y) memset(x,y,sizeof(x))
#define SIZE 1000
struct node{
    int v,nxt,cap,cost;//指向那个点 下条边id 流通容量 这条路花费(看情况有时候是单价,记得改dfs里面的跟新)
}edge[40010];
int head[SIZE],dis[SIZE],pre[SIZE],ecnt,s,t;
bool vst[SIZE];
inline void init(){
    ecnt=0;//从偶数开始都行
    mem(head,-1);
}
inline void addedge(int u,int v,int cap,int cost){
    edge[ecnt].v=v;
    edge[ecnt].cap=cap;
    edge[ecnt].cost=cost;
    edge[ecnt].nxt=head[u];
    head[u]=ecnt;
    ecnt++;
    swap(u,v);//添加反边
    edge[ecnt].v=v;
    edge[ecnt].cap=0;
    edge[ecnt].cost=-cost;//注意反边花费为负
    edge[ecnt].nxt=head[u];
    head[u]=ecnt;
    ecnt++;
}
bool spfa(){
    mem(dis,INF);//不能少
    mem(vst,0);
    mem(pre,-1);
    dis[s]=0;//s是起点,t是终点,分层
    vst[s]=true;
    queue<int> que;
    que.push(s);
    while(!que.empty()){
        int u=que.front();que.pop();
        vst[u]=false;
        for(int i=head[u];i!=-1;i=edge[i].nxt){
            if(dis[u]+edge[i].cost<dis[edge[i].v]&&edge[i].cap>0){
                //通过点u更短
                dis[edge[i].v]=dis[u]+edge[i].cost;
                pre[edge[i].v]=i;
                if(!vst[edge[i].v]){
                    vst[edge[i].v]=true;
                    que.push(edge[i].v);
                }
            }
        }
    }
    return pre[t]!=-1;//没有办法从s到t返回false
}
int mfmc(int & cost){//cost 按引用更新
    int flow=0; cost=0;
    while (spfa()) {
        int Min=INF;
        for(int i=pre[t];i!=-1;i=pre[edge[i^1].v]){//i是边的id,得到另一个顶点edge[i^1].v
            if(Min>edge[i].cap){
                Min=edge[i].cap;
            }
        }
        for(int i=pre[t];i!=-1;i=pre[edge[i^1].v]){
            edge[i].cap-=Min;
            edge[i^1].cap+=Min;

        }
        cost+=dis[t]*Min;
        flow+=Min;
    }
    return flow;
}