抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

网络流模板

-模板

发布于：2024年2月29日

字数：2.1k 字

时长：12 分钟

最大流_dinic

EK算法

由于最大流中一定没有增广路由于最大流中一定没有增广路

可以不断从源点出发寻找增广路可以不断从源点出发寻找增广路

并在残余网络上修改并在残余网络上修改

直到不存在增广路为止

dinic

由于EK每次只能搜索1条增广路

在EK算法的基础上,建立分层图,并搜索多条增广路

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
/*
g++ -o2 w.cpp -o c -std=c++14
.\c

*/


bool bfs(ll start,ll to){
    ll fron=0;
    ll back=1;
    memset(dep,-1,sizeof(dep));
    q[fron]=start;
    cur[start]=head[start];//弧优化
    dep[start]=0;
    while(fron!=back){
        ll x=q[fron++];
        if(fron==N)fron=0;
        for(ll i=head[x];~i;i=e[i].next){
            ll y=e[i].y;
            ll f=e[i].f;
            ll w=e[i].w;
            if(dep[y]==-1 && f){
                dep[y]=dep[x]+1;
                cur[y]=head[y];//记录弧
                if(y==to)return true;
                q[back++]=y;
                if(back==N)back=0;
            }
        } 
    }
    return false;
}

ll find(ll x,ll to,ll limit){
    if(x==to)return limit;
    ll flow=0;
    for(ll i=cur[x];~i && flow<limit;i=e[i].next){
        ll y=e[i].y;
        ll f=e[i].f;
        ll w=e[i].w;
        cur[x]=i;
        if(dep[y]==dep[x]+1 && f){
            //如果不是相邻的层就不继续
            //当权值不大于零时，不符合流限制
            ll t=find(y,to,min(limit-flow,f));
            if(!t)dep[y]=-1;//废点优化
            e[i].f-=t;
            e[ops(i)].f+=t;
            flow+=t;
        }
    }
    return flow;
}

ll dinic(ll start,ll to){
    ll flow;
    ll r=0;
    //先找增广路径
    //再深搜求该路径最大可行流
    while(bfs(start,to))
        while(flow=find(start,to,inf))
            r+=flow;
    return r;
}


ISAP

在 的基础上在进行优化,优化掉了多次寻找增广路的过程

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
inline bool bfs(int start,int to){
    int fron=0;
    int back=1;
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    q[fron]=to;
    dep[to]=0;
    gap[0]=1;
    while(fron!=back){
        int x=q[fron++];
        if(fron==N)fron=0;
        for(int i=head[x];~i;i=e[i].next){
            int y=e[i].y;
            int f=e[i].f;
            if(dep[y]==-1){
                dep[y]=dep[x]+1;
                gap[dep[y]]++;
                q[back++]=y;
                if(back==N)back=0;
            }
        } 
    }
    return false;
}

inline ll find(int x,int to,ll limit){
    if(x==to)return limit;
    ll flow=0;
    for(int i=cur[x];~i;i=e[i].next){
        int y=e[i].y;
        int f=e[i].f;
        cur[x]=i;
        if(!f)continue;
        if(dep[y]+1==dep[x]){
            ll t=find(y,to,min(limit-flow,f));
            if(t>0){
                e[i].f-=t;
                e[ops(i)].f+=t;
                flow+=t;
            }
            if(flow==limit)return flow;
        }
    }
    gap[dep[x]]--;
    if(!gap[dep[x]])dep[s]=n+1;
    dep[x]++;
    gap[dep[x]]++;
    return flow;
}

inline ll ISAP(int start,int to){
    ll flow=0;
    bfs(start,to);
    while(dep[s]<n){
        memcpy(cur,head,sizeof(head));
        flow+=find(start,to,inf);
    }        
    return flow;
}

无源汇上下界可行流

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

int main(){
    scanf("%d%d",&n,&m);
    init();
    for(int i=1;i<=m;i++){
        int x,y,c,w;
        scanf("%d%d%d%d",&x,&y,&c,&w);
        make(x,y,c,w);
        erz[x]-=c;
        erz[y]+=c;
    }
    for(int i=1;i<=n;i++){
        if(erz[i]>0){
            make(s,i,0,erz[i]);
            sum+=erz[i];
        }
        if(erz[i]<0)make(i,t,0,-erz[i]);
    }

    int ans=dinic(s,t);

    // printf("%d \n%d \n",ans,sum);
    if(ans==sum){
        printf("YES\n");
        for(int i=0;i<m*2;i+=2){
            int w=e[ops(i)].w;
            int l=e[i].v;
            printf("%d\n",w+l);
        }
    }
    else printf("NO");
    return 0;
}

有源汇上下界最大流

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

int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    init();
    for(int i=1;i<=m;i++){
        int x,y,c,w;
        scanf("%d%d%d%d",&x,&y,&c,&w);
        erz[x]-=c;erz[y]+=c;
        make(x,y,c,w);
    }
    for(int i=1;i<=n;i++){
        if(erz[i]>0){
            make(S,i,0,erz[i]);
            sum+=erz[i];
        }
        if(erz[i]<0)make(i,T,0,-erz[i]);
    }
    make(t,s,0,inf);
    int cnt=dinic(S,T);
    if(cnt<sum){
        printf("No Solution\n");
        return 0;
    }
    int res=e[tot-1].w;
    e[tot-1].w=0;
    e[tot-2].w=0;
    int ans=dinic(s,t);
    printf("%d\n",res+ans);
    return 0;
}

有源汇上下界最小流

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
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    init();
    for(int i=1;i<=m;i++){
        int x,y,c,w;
        scanf("%d%d%d%d",&x,&y,&c,&w);
        erz[x]-=c;erz[y]+=c;
        make(x,y,c,w);
    }
    for(int i=1;i<=n;i++){
        if(erz[i]>0){
            make(S,i,0,erz[i]);
            sum+=erz[i];
        }
        if(erz[i]<0)make(i,T,0,-erz[i]);
    }
    make(t,s,0,inf);
    int cnt=dinic(S,T);
    if(cnt<sum){
        printf("No Solution\n");
        return 0;
    }
    int res=e[tot-1].w;
    e[tot-1].w=0;
    e[tot-2].w=0;
    int ans=dinic(t,s);
    printf("%d\n",res-ans);
    return 0;
}

费用流

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/*
g++ -o2 2174.cpp -o c -std=c++14
.\c

*/

#include<cstring>
#include<cstdio>

using namespace std;
const int N=1e6+100;
const int M=1e3+100;
const int inf=0x3f3f3f3f;

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
int ops(int x){return x^1;}

int tot;
int head[N];

struct node{
    int y,w,f,next;
}e[N];

int pre[N];
int dis[N];
int flo[N];
int vis[N];
int q[N];

int n,m,s,t;

void add(int x,int y,int f,int w){
    e[tot].y=y;
    e[tot].f=f;
    e[tot].w=w;
    e[tot].next=head[x];
    head[x]=tot++;
    return ;
}

void make(int x,int y,int f,int w){
    add(x,y,f,w);
    add(y,x,0,-w);
    return ;
}

bool spfa(int start,int to){
    int fron=0;
    int back=1;
    memset(dis,0x3f,sizeof(dis));
    memset(flo,0,sizeof(flo));
    q[fron]=start;
    dis[start]=0;
    flo[start]=inf;
    while(fron!=back){
        int x=q[fron++];
        if(fron==N)fron=0;
        vis[x]=0;
        // printf("%d\n",x);
        for(int i=head[x];~i;i=e[i].next){
            int y=e[i].y;
            int w=e[i].w;
            int f=e[i].f;
            if(f && dis[y]>dis[x]+w){
                flo[y]=min(flo[x],f);
                dis[y]=dis[x]+w;
                pre[y]=i;
                if(!vis[y]){
                    q[back++]=y;
                    if(back==N)back=0;
                    vis[y]=true;
                }
            }
        }
    }
    return flo[to]>0;
}

void EK(int &flow,int &cost,int start,int to){
    flow=0;
    cost=0;
    while(spfa(start,to)){
        int t=flo[to];
        flow+=t;
        cost+=t*dis[to];
        for(int i=to;i!=start;i=e[ops(pre[i])].y){
            e[pre[i]].f-=t;
            e[ops(pre[i])].f+=t;
        }
    }
    return ;
}

void init(){
    memset(head,-1,sizeof(head));
    return ;
}

int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    init();
    for(int i=1;i<=m;i++){
        int x,y,w,f;
        scanf("%d%d%d%d",&x,&y,&f,&w);
        make(x,y,f,w);
    }
    // printf("%d\n",tot);
    int flow;
    int cost;
    EK(flow,cost,s,t);
    printf("%d %d\n",flow,cost);
    return 0;
}

Primal-Dual 原始对偶算法

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
/*
g++ -o2 dij_fei.cpp -o c -std=c++14
.\c

*/


#include<cstring>
#include<cstdio>
#include<queue>
// #include<vector>

using namespace std;

const int N=5e3+100;
const int M=1e6+100;
const int inf=0x3f3f3f3f;

int tot;
int head[N];
struct edge{
    // int x;
    int y;
    int f,w;
    int next;
}e[M];

struct node{
    int x,w;
    bool operator <(const node &s)const{
        return w > s.w;
    }
};

int cnt[N];
int tmp[N];
int vis[N];

int pre[N];
int dis[N];
int flo[N];

int n,m;
int s,t;

inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline int ops(int x){return x^1;}

inline void init(){
    tot=0;
    memset(head,-1,sizeof(head));
    return ;
}

inline void add(int x,int y,int f,int w){
    e[tot].y=y;
    e[tot].f=f;
    e[tot].w=w;
    e[tot].next=head[x];
    head[x]=tot++;
}

inline void make(int x,int y,int f,int w){
    add(x,y,f,w);
    add(y,x,0,-w);
    return ;
}

inline void spfa(int start,int to){
    memset(tmp,0x3f,sizeof(tmp));
    queue<int>q;
    q.push(start);
    tmp[start]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        vis[x]=0;
        for(int i=head[x];~i;i=e[i].next){
            int y=e[i].y;
            int f=e[i].f;
            int w=e[i].w;
            if(!f)continue;
            if(tmp[x]+w<tmp[y]){
                tmp[y]=tmp[x]+w;
                if(!vis[y]){
                    vis[y]=1;
                    q.push(y);
                }
            }
        }
    }
    return ;
}

inline bool dij(int start,int to){
    priority_queue<node>q;
    for(int i=1;i<=n;i++){
        dis[i]=inf;
        flo[i]=0;
        vis[i]=0;
    }
    dis[start]=0;
    flo[start]=inf;
    q.push(node{start,dis[start]});
    while(!q.empty()){
        int x=q.top().x;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];~i;i=e[i].next){
            int y=e[i].y;
            int f=e[i].f;
            int w=e[i].w+tmp[x]-tmp[y];
            if(!f)continue;
            if(dis[y]>dis[x]+w){
                flo[y]=min(flo[x],f);
                dis[y]=dis[x]+w;
                pre[y]=i;
                q.push(node{y,dis[y]});
            }
        }
    }
    return flo[to]>0;
}

inline void EK(int start,int to,int &flow,int &cost){
    flow=0;
    cost=0;
    while(dij(start,to)){
        int t=flo[to];
        flow+=t;
        cost+=t*(dis[to]-tmp[start]+tmp[to]);
        for(int i=to;i!=start;i=e[ops(pre[i])].y){
            e[pre[i]].f-=t;
            e[ops(pre[i])].f+=t;
        }
        for(int i=1;i<=n;i++){
            if(dis[i]<inf){
                tmp[i]+=dis[i];
            }
        }
    }
    return ;
}

int main(){
    init();
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        int x,y,f,w;
        scanf("%d%d%d%d",&x,&y,&f,&w);
        make(x,y,f,w);
    }
    spfa(s,t);
    int flow=0;
    int cost=0;
    EK(s,t,flow,cost);
    printf("%d %d\n",flow,cost);
    return 0;
}

debug_

1
2
3
4
5
6
7
8
9
10
11
12
void debug_build(){
    printf("\n");
    printf("%d\n",tot);
    for(int i=0;i<tot;i+=2){
        int x=e[ops(i)].y;
        int y=e[i].y;
        int w=e[i].w;
        printf("%d -> %d : %d\n",x,y,w);
    }
    printf("\n");
    return ;
}

本页文档最后更新于：2025年1月22日