最小费用最大流

2023-08-16
作者没进水的脑子
~8.68K 字

1. 费用流问题
1. 1.1. 前言
2. 1.2. 费用流问题

费用流问题

前言

依旧是填坑，讲解最小费用最大流的解决方法，对最大流不熟悉的同学可以看我的前几篇文章。

费用流问题

一个网络流的扩展问题，从名字中就能看出，就是在容量限制的基础上加上经过每条边需要花费的费用。最小费用最大流问题就是为了解决在给的流量F时最小的花费，未指定F时则求流量最大时的最小花费。各位神犇可以思考一下该以何种顺序搜索。

思想

不难看出，有以下两种搜索顺序：

1.先找最大流，然后再不断缩小花费
2.先找最短路（最小花费），再在路径上不断增加流量。

很明显第二种搜索顺序更容易理解，代码也容易实现。下面详细说明该思想的实现方法。

实现方法

首先，我们要找最短路。让我们回忆一下最短路算法都有哪些，你应该马上能想到Floyd、Bellman—Ford、SPFA和Dijkstra算法。这些都可以用吗？想想处理残留网络的过程，会在流经的边上建立一条反向边，那么反向边的花费一定与其正向边相反，因此我们要处理负权变，那么似乎Dijkstra就不能用了。因此我们选择Bellman—Ford或SPFA算法（Floyd复杂度太高）。找到最短路径之后我们记录一下路径，以便之后最大流处理。
其次就是处理最大流了。最大流算法上就没什么限制，Edmonds-Karp、Dinic、ISAP、HLPP都可以，用自己拿手的（复杂度小的）写就行。

SPFA+Dinic:

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 0x3f3f3f3f;
const int N = 5e3 + 10;
const int M = 1e5 + 10;
int head[N];
int cnt = 1;
int now[N];
int s, t, n, m;
struct edge
{
    int u, v, c, val, nxt;
    edge(int u = 0, int v = 0, int c = 0, int val = 0, int nxt = 0) : u(u), v(v), c(c), val(val), nxt(nxt) {}
} e[M];
void ADD(int u, int v, int c, int val)
{
    cnt++;
    e[cnt] = edge(u, v, c, val, head[u]);
    head[u] = cnt;
}
void add_edge(int u, int v, int c, int val)
{
    ADD(u, v, c, val);
    ADD(v, u, 0, -val);
}
int dis[N];
bool vis[N];
int pre[N];
int flow[N];
bool spfa(int s, int t)
{
    for (int i = 1; i <= n; i++)
        dis[i] = inf;
    memset(flow, 0, sizeof flow);
    memset(vis, 0, sizeof vis);
    memcpy(now, head, sizeof head);
    dis[s] = 0;
    vis[s] = 1;
    flow[s] = inf;
    queue<int> q;
    q.push(s);
    while (!q.empty())
    {
        int u = q.front();
        vis[u] = 0;
        q.pop();
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            int c = e[i].c;
            int val = e[i].val;
            if (c && dis[v] > dis[u] + val)
            {
                dis[v] = dis[u] + val;
                flow[v] = min(c, flow[u]);
                pre[v] = i;
                if (vis[v])
                    continue;
                q.push(v);
                vis[v] = 1;
            }
        }
    }
    return flow[t] > 0;
}
int cost, maxflow;
int Dinic(int u, int t, int flow)
{
    if (u == t)
        return flow;
    vis[u] = 1;
    int nowflow = 0;
    for (int i = now[u]; i; i = e[i].nxt)
    {
        now[u] = i;
        int v = e[i].v;
        if (dis[v] == dis[u] + e[i].val && e[i].c && !vis[v])
        {
            int ff = Dinic(v, t, min(flow - nowflow, e[i].c));
            if (ff)
                cost += ff * e[i].val, e[i].c -= ff, e[i ^ 1].c += ff, nowflow += ff;
        }
    }
    vis[u] = 0;
    return nowflow;
}
void EK(int &maxflow, int &cost)
{
    maxflow = cost = 0;
    while (spfa(s, t))
    {
        int ff = flow[t];
        maxflow += ff;
        cost += ff * dis[t];
        for (int u = t; u != s; u = e[pre[u]].u)
        {
            int i = pre[u];
            e[i].c -= ff;
            e[i ^ 1].c += ff;
        }
    }
}
signed main()
{
    cin >> n >> m >> s >> t;
    for (int i = 1; i <= m; i++)
    {
        int u, v, c, val;
        cin >> u >> v >> c >> val;
        add_edge(u, v, c, val);
    }
     while(spfa(s,t)){
        memset(vis,0,sizeof vis);
        maxflow+=Dinic(s,t,inf);
    } 
   // EK(maxflow, cost);
    cout << maxflow << " " << cost;
}

SPFA+EK

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int M = 1e5 + 10;
const int N = 5e3 + 10;
const int inf = 0x3f3f3f3f;
int cnt = 1;
int head[N];
int n, m, s, t;
struct edge
{
    int u, v, c, val, nxt;
    edge(int u = 0, int v = 0, int c = 0, int val = 0, int nxt = 0) : u(u), v(v), c(c), val(val), nxt(nxt) {}
} e[M];
void Add(int u, int v, int c, int val)
{
    cnt++;
    e[cnt]=edge(u,v,c,val,head[u]);
    head[u]=cnt;
}
void add_edge(int u,int v,int c,int val){
    Add(u,v,c,val);
    Add(v,u,0,-val);
}
int dis[N];
int pre[N];
int flow[N];
bool vis[N];
bool spfa(int s,int t){
    for(int i=1;i<=n;i++) dis[i]=inf;
    memset (vis,0,sizeof vis);
    memset (flow ,0,sizeof flow);
    dis[s]=0;
    vis[s]=1;
    flow[s]=inf;
    queue<int>q;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v;
            int c=e[i].c;
            int val=e[i].val;
            if(dis[v]>dis[u]+val&&c) {
                dis[v]=dis[u]+val;
                flow[v]=min(flow[u],c);
                pre[v]=i;
                if(!vis[v]){
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return flow[t]>0;
}
void EK(int &maxflow,int &cost) {
    maxflow=cost=0;
    while(spfa(s,t)) {
        int ff=flow[t];
        maxflow+=ff;
        cost+=ff*dis[t];
        for(int u=t;u!=s;u=e[pre[u]].u){
            int i=pre[u];
            e[i].c-=ff;
            e[i^1].c+=ff;
        }
    }
}
signed main()
{
    cin >> n >> m >> s >> t;
    for(int i=1;i<=m;i++){
        int u,v,c,val;
        cin>>u>>v>>c>>val;
        add_edge(u,v,c,val);
    }
    int ans1,ans2;
    EK(ans1,ans2);
    cout<<ans1<<" "<<ans2;
}

题外话

大家都知道，Dijkstra无法处理负权变，这样无法保证其贪心的正确性。不过，我们可以引入“势能”的概念，动态的维护每个边的边长，来保证Dijkstra的正确性。感兴趣的话可以去看《挑战程序设计》或者自行搜索。这里不做过多介绍了，只给出代码供大家参考。

Code(P2153[SDOI2009]晨跑代码)

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 420;
const int M = 1e5 + 10;
const int inf = 0x3f3f3f3f;
struct edge
{
    int u, v, c, val, nxt;
    edge(int u = 0, int v = 0, int c = 0, int val = 0, int nxt = 0) : u(u), v(v), c(c), val(val), nxt(nxt) {}
} e[M];
int head[N];
int now[N];
int pre[N];
int h[N];
int dis[N];
int cnt = 1;
void add(int u, int v, int c, int val)
{
    cnt++;
    e[cnt] = edge(u, v, c, val, head[u]);
    head[u] = cnt;
}
void add_edge(int u, int v, int c, int val)
{
    add(u, v, c, val);
    add(v, u, 0, -val);
}
int n, m;
int s, t;
struct Node
{
    int name;
    int dis;
    Node(int name, int dis) : name(name), dis(dis) {}
    bool operator<(const Node &a) const
    {
        return dis > a.dis;
    }
};
bool dj()
{
    priority_queue<Node> q;
    for (int i = 1; i <= 2 * n; i++)
        dis[i] = inf;
    memcpy(now, head, sizeof(head));
    dis[s] = 0;
    q.push(Node(s, dis[s]));
    while (!q.empty())
    {
        int u = q.top().name;
        int d = q.top().dis;
        q.pop();
        if (dis[u] < d)
            continue;
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            int val = e[i].val;
            int c = e[i].c;
            if (!c)
                continue;
            if (dis[v] > dis[u] + val + h[u] - h[v])
            {
                dis[v] = dis[u] + h[u] - h[v] + val;
                pre[v] = i;
                q.push(Node(v, dis[v]));
            }
        }
    }
    return dis[t] == inf;
}
int mx = 0, mn = 0;
bool vis[N];
int dfs(int u, int t, int flow)
{
    if (u == t)
        return flow;
    vis[u] = 1;
    int nowflow = 0;
    for (int i = now[u]; i; i = e[i].nxt)
    {
        now[u] = i;
        int v = e[i].v;
        if (!vis[v] && e[i].c && dis[v] == dis[u] + h[u] - h[v] + e[i].val)
        {
            int ff = dfs(v, t, min(e[i].c, flow ));
            if (ff)
                mn += ff * e[i].val, e[i].c-=ff,e[i^1].c+=ff,nowflow+=ff,flow-=ff;
        }
    }
    vis[u]=0;
    return nowflow;
}
void work()
{
    memset(h, 0, sizeof h);
    int flow = inf;
    while (flow)
    {
        if (dj())
            break;
        int nowflow;
        while((nowflow=dfs(s,t,inf))) mx+=nowflow;
        for (int i = 1; i <= 2 * n; i++)
            h[i] += (dis[i] == inf) ? 0 : dis[i];
        
    }
    cout << mx << " " << mn;
}
signed main()
{
    cin >> n >> m;
    s = n + 1;
    t = n;
    for (int i = 1; i <= m; i++)
    {
        int u, v, val;
        scanf("%lld%lld%lld", &u, &v, &val);
        add_edge(u + n, v, 1, val);
    }
    for (int i = 1; i <= n; i++)
    {
        add_edge(i, i + n, 1, 0);
    }
    work();
}

没进水的脑子

费用流问题

前言

费用流问题

思想

实现方法

题外话