题目描述

给定一个包含 n 个点 m 条边的有向图，并给定每条边的容量和费用，边的容量非负。

图中可能存在重边和自环，保证费用不会存在负环。

求从 S 到 T 的最大流，以及在流量最大时的最小费用。

输入格式
第一行包含四个整数 n,m,S,T。

接下来 m 行，每行三个整数 u,v,c,w，表示从点 u 到点 v 存在一条有向边，容量为 c，费用为 w。

点的编号从 1 到 n。

输出格式
输出点 S 到点 T 的最大流和流量最大时的最小费用。

如果从点 S 无法到达点 T 则输出 0 0。

数据范围
2≤n≤5000,
1≤m≤50000,
0≤c≤100,
−100≤w≤100
S≠T

样例

输入样例：
5 5 1 5
1 4 10 5
4 5 5 10
4 2 12 5
2 5 10 15
1 5 10 10
输出样例：
20 300

算法1

(暴力枚举) $O(n^2)$

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1e6+40;
const int inf = 0x3f;
int n,m,s,t,idx = 1;
int maxflow,mincost;

int dis[N << 1],head[N << 1],dep[N << 1],pre[N << 1];
bool vis[N << 1];
struct edge{
    int next;
    int to;
    int dis;
    int flow;
}e[N << 1];
void add(int u,int v,int flow,int dis)
{
    idx++;
    e[idx].to = v;
    e[idx].dis = dis;
    e[idx].flow = flow;
    e[idx].next = head[u];
    head[u] = idx;
}

bool spfa()
{
    queue<int>q;
    memset(dis, inf, sizeof dis);
    memset(vis,0,sizeof(vis));
    q.push(s);
    dis[s] = 0;
    vis[s] = 1;
    dep[s] = 1 << 30;
    while(q.size())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for(int i = head[u];i; i = e[i].next)
        {
            if(!e[i].flow) continue;
            int v = e[i].to;
            if(dis[v] > dis[u] + e[i].dis)
            {
                dis[v] = dis[u] + e[i].dis;
                dep[v] = min(dep[u], e[i].flow);
                pre[v] = i;
                if(!vis[v])
                {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    if(dis[t] == 0x3f3f3f3f) return 0;
    return 1;
}

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

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