网络流初步

网络流初步

最大流

  • FF算法
  • 每次深搜找一条增广路从S到T,减去当前边的容量,并且建立反悔边,直到原图中没有从S到T的增广路。
  • 代码:
    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
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;

    int n, m, S, T;
    struct Edge{
    int to, nxt;
    ll w;
    }e[200009];
    int head[10009], tot = 1;
    bool vis[10009];

    void add(int x, int y, ll w){
    e[++tot].to = y;
    e[tot].w = w;
    e[tot].nxt = head[x];
    head[x] = tot;
    }

    ll dfs(int x, ll now){
    if(x == T) return now;
    for(int i = head[x]; i; i = e[i].nxt){
    int y = e[i].to;
    ll w = e[i].w;
    if(w == 0 || vis[y]) continue;
    vis[y] = 1;
    ll res = 0;
    if((res = dfs(y, min(now, w))) > 0){
    e[i].w -= res;
    e[i^1].w += res;
    return res;
    }
    }
    return 0;
    }

    int main(){
    scanf("%d%d%d%d", &n, &m, &S, &T);
    for(int i = 1; i <= m; i++){
    int x, y;
    ll w;
    scanf("%d%d%lld", &x, &y, &w);
    add(x, y, w);
    add(y, x, 0);
    }
    ll ans = 0;
    while(1){
    memset(vis, 0, sizeof(vis));
    ll res = dfs(S, 0x3f3f3f3f3f3f3f3f);
    if(res == 0) break;
    ans += res;
    }
    printf("%lld\n", ans);
    return 0;
    }

  • EK算法
  • 和FF算法几乎一样,只是把找增广路变成宽搜就好。
  • 代码:
    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
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;


    int n, m, S, T;
    struct Edge{
    int to, nxt;
    ll w;
    }e[200009];
    int head[10009], tot = 1;
    int dep[10009];

    void add(int x, int y, ll w){
    e[++tot].to = y;
    e[tot].w = w;
    e[tot].nxt = head[x];
    head[x] = tot;
    }

    bool bfs(){
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    dep[S] = 1;
    q.push(S);
    while(!q.empty()){
    int x = q.front();
    q.pop();
    for(int i = head[x]; i; i = e[i].nxt){
    int y = e[i].to;
    ll w = e[i].w;
    if(w == 0 || dep[y]) continue;
    dep[y] = dep[x] + 1;
    q.push(y);
    }
    }
    return dep[T];
    }

    ll dfs(int x, ll now){
    if(x == T) return now;
    ll out = 0;
    for(int i = head[x]; i; i = e[i].nxt){
    int y = e[i].to;
    ll w = e[i].w;
    if(w == 0) continue;
    if(dep[y] != dep[x] + 1) continue;
    ll res = 0;
    if((res = dfs(y, min(now, w))) > 0){
    e[i].w -= res;
    e[i^1].w += res;
    out += res;
    now -= res;
    }
    }
    if(out == 0) dep[x] = 0;
    return out;
    }

    int main(){
    scanf("%d%d%d%d", &n, &m, &S, &T);
    for(int i = 1; i <= m; i++){
    int x, y;
    ll w;
    scanf("%d%d%lld", &x, &y, &w);
    add(x, y, w);
    add(y, x, 0);
    }
    ll ans = 0;
    while(1){
    if(!bfs()) break;

    ans += dfs(S, 0x3f3f3f3f3f3f3f3f);
    }
    printf("%lld\n", ans);
    return 0;
    }

  • Dinic算法

  • 这个算法效率比较高,主要有下面几个优化:

    1. 建立分层图,每一步只能从当前层走向下一层,优化很多。
    2. 从当前点开始,计算所能走到T的所有增广路之后再回溯,减少搜索重复部分。
    3. 如果当前点没有能到达T的增广路,删去当前点。
  • 代码:

    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
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;

    int n, m, S, T;
    struct Edge{
    int to, nxt;
    ll w;
    }e[200009];
    int head[10009], tot = 1;
    int dep[10009];

    void add(int x, int y, ll w){
    e[++tot].to = y;
    e[tot].w = w;
    e[tot].nxt = head[x];
    head[x] = tot;
    }

    bool bfs(){
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    dep[S] = 1;
    q.push(S);
    while(!q.empty()){
    int x = q.front();
    q.pop();
    for(int i = head[x]; i; i = e[i].nxt){
    int y = e[i].to;
    ll w = e[i].w;
    if(w == 0 || dep[y]) continue;
    dep[y] = dep[x] + 1;
    q.push(y);
    }
    }
    return dep[T];
    }

    ll dfs(int x, ll now){
    if(x == T) return now;
    ll out = 0;
    for(int i = head[x]; i; i = e[i].nxt){
    int y = e[i].to;
    ll w = e[i].w;
    if(w == 0) continue;
    if(dep[y] != dep[x] + 1) continue;
    ll res = 0;
    if((res = dfs(y, min(now, w))) > 0){
    e[i].w -= res;
    e[i^1].w += res;
    out += res;
    now -= res;
    }
    }
    if(out == 0) dep[x] = 0;
    return out;
    }

    int main(){
    scanf("%d%d%d%d", &n, &m, &S, &T);
    for(int i = 1; i <= m; i++){
    int x, y;
    ll w;
    scanf("%d%d%lld", &x, &y, &w);
    add(x, y, w);
    add(y, x, 0);
    }
    ll ans = 0;
    while(1){
    if(!bfs()) break;
    ans += dfs(S, 0x3f3f3f3f3f3f3f3f);
    }
    printf("%lld\n", ans);
    return 0;
    }

费用流

  • 费用流是网络流上加费用的一类问题,每个边有一个费用,流过这条边需要支付流过这条边的流量$\times$当前边的v的费用,我们想要在保证最大流的前提下使费用尽可能多或者少。

  • MCMF算法

  • 只需要将原来的EK算法的bfs改为SPFA即可, 由于网络流中可能会有负权边,所以不能使用dijkstra算法求最短路。

  • 代码:

    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
    #include<bits/stdc++.h>
    using namespace std;

    const int INF = 0x3f3f3f3f;

    int n, m, s, t;
    struct Edge{
    int to, nxt, w, v;
    }e[400009];
    int head[20009], tot = 1;
    int pre[20009], flw[20009];
    bool vis[20009];
    int dis[20009];
    int maxflow, mincost;

    void add(int x, int y, int w, int v){
    e[++tot].to = y;
    e[tot].w = w;
    e[tot].nxt = head[x];
    head[x] = tot;
    e[tot].v = v;
    }

    bool bfs(){
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    memset(flw, 0x3f, sizeof(flw));
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    while(!q.empty()){
    int x = q.front();
    q.pop();
    vis[x] = 0;
    for(int i = head[x]; i; i = e[i].nxt){
    int y = e[i].to, w = e[i].w, v = e[i].v;
    if(w > 0 && dis[y] > dis[x] + v){
    dis[y] = dis[x] + v;
    flw[y] = min(flw[x], w);
    pre[y] = i;
    if(!vis[y]){
    vis[y] = 1;
    q.push(y);
    }
    }
    }
    }
    return flw[t] != 0x3f3f3f3f;
    }

    void update(){
    int x = t;
    maxflow += flw[t];
    mincost += flw[t] * dis[t];
    while(x != s){
    int i = pre[x];
    e[i].w -= flw[t];
    e[i^1].w += flw[t];
    x = e[i^1].to;
    }
    }

    int main(){
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i = 1; i <= m; i++){
    int x, y, w, v;
    scanf("%d%d%d%d", &x, &y, &w, &v);
    add(x, y, w, v);
    add(y, x, 0, -v);
    }
    while(bfs()) update();
    printf("%d %d\n", maxflow, mincost);
    return 0;
    }

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×