【模板】网络最大流 + 最小费用最大流

71 阅读 0 评论 47 点赞

我是靠谱客的博主英俊小霸王，最近开发中收集的这篇文章主要介绍【模板】网络最大流 + 最小费用最大流，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：P3376 【模板】网络最大流

这几天敲了几遍最大流的板子，还是有一些细节处理不好
在这里总结一下

前向星开边的数组的时候记得要开大一点，然后记得初始化head数组与tot
dfs的时候应该是这篇文章下面贴的代码稍微快一点
level数组的用途是判断层次，初始化的值可以灵活变化，不作要求
tot的值一定要初始化为0
原因：

在dfs的时候我们要用到正向边减流，反向边加流，我们是用当前边的编号异或1去找与当前边反向的边的编号的
在tot值初始为0的情况下，拿建立的第一条边来说，他的编号是0，他的反向边编号为0+1 = 1，第二条边，编号为2，反向边编号为2+1 = 3……
偶数异或1相当于加1，奇数异或1相当于减一，这正好符合我们建边时候的顺序

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 1e5;

struct node
{
    int c;
    int to;
    int next;
} edge[N*10];

int n,m,tot;
int head[N];
int level[N];

void add(int u, int v, int w)
{
    edge[tot].c = w;
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;

    edge[tot].c = 0;
    edge[tot].to = u;
    edge[tot].next = head[v];
    head[v] = tot++;
}

int bfs(int s, int d)
{
    for(int i = 0; i <= n; i++)
    {
        level[i] = -1;
    }
    level[s] = 0;
    queue<int> q;
    q.push(s);
    while(q.size())
    {
        int u = q.front();
        if(u == d) return 1;
        q.pop();
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].to;
            int c = edge[i].c;
            if(level[v] == -1 && c)
            {
                level[v] = level[u]+1;
                q.push(v);
            }
        }
    }
    return 0;
}

int dfs(int u, int d, int f)
{
    if(u == d) return f;
    int t = 0;
    int tmp;
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        int v = edge[i].to;
        int c = edge[i].c;
        if(c && level[v] == level[u]+1 && (tmp = dfs(v, d, min(f, c))))
        {
            edge[i].c -= tmp;
            edge[i^1].c += tmp;
            t += tmp;
            f -= tmp;
            if(!f) break;
        }
    }
    if(t) return t;
    level[u] = -1;
    return 0;
}

int Dinic(int s, int d)
{
    int ans = 0;
    while(bfs(s, d))
    {
        int tmp = dfs(s, d, inf);
        if(!tmp) break;
        ans += tmp;
    }
    return ans;
}

int main()
{
    int s,d,u,v,w;
    scanf("%d %d %d %d",&n,&m,&s,&d);
    tot = 0;
    for(int i = 0; i <= n; i++)
    {
        head[i] = -1;
    }
    while(m--)
    {
        scanf("%d %d %d",&u,&v,&w);
        if(u == v) continue;
        add(u, v, w);
    }
    printf("%dn",Dinic(s, d));
    return 0;
}

最小费用最大流

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#define inf 0x3f3f3f3f
using namespace std;

typedef long long ll;

const int N = 500010;

struct node
{
    int w,c;
    int to;
    int next;
} edge[N];

int n;
int pre[N];
int vis[N];
int dis[N];
int head[N],tot;

void add(int u, int v, int c, int w)
{
    edge[tot].c = c;
    edge[tot].w = w;
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;

    edge[tot].c = 0;
    edge[tot].w = -w;
    edge[tot].to = u;
    edge[tot].next = head[v];
    head[v] = tot++;
}

int spfa(int s, int d)
{
    memset(pre, -1, sizeof(pre));
    memset(vis, 0, sizeof(vis));
    memset(dis, inf, sizeof(dis));
    vis[s] = 1;
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    while(q.size())
    {
        int u = q.front();
        vis[u] = 0;
        q.pop();
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            if(edge[i].c)
            {
                int v = edge[i].to;
                int w = edge[i].w;
                if(dis[v] > dis[u] + w)
                {
                    dis[v] = dis[u] + w;
                    pre[v] = i;
                    if(!vis[v])
                    {
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
        }
    }
    return pre[d] != -1;
}

void mcmf(int s, int d)
{
    int ans = 0;
    int tot = 0;
    while(spfa(s, d))
    {
        int tmp = inf;
        for(int i = d; i != s; i = edge[pre[i]^1].to)
        {
            tmp = min(edge[pre[i]].c, tmp);
        }
        tot += tmp;
        for(int i = d; i != s; i = edge[pre[i]^1].to)
        {
            edge[pre[i]].c -= tmp;
            edge[pre[i]^1].c += tmp;
            ans += edge[pre[i]].w*tmp;
        }
    }
    printf("%d %dn",tot, ans);
}

int main()
{
    int m,u,v,w,c,s,d;
    tot = 0;
    memset(head, -1, sizeof(head));
    scanf("%d %d %d %d",&n,&m,&s,&d);
    while(m--)
    {
        scanf("%d %d %d %d",&u,&v,&c,&w);
        add(u, v, c, w);
    }
    mcmf(s, d);
    return 0;
}