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;
}
|
多路增广+当前弧优化
建图时候建反向边（前向星边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;
}
|
求最小费用最大流
建边时候反边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;
}
|