题目描述

这是一道模板题。

给定一个图，每条边有容量和费用，使用每条边的单位流量需要支付特定的费用。给定源点 $1$ 和汇点 $n$，求图的最大流和最大流需要支付的最小费用。

输入格式

第一行两个整数 $n$、$m$，表示有 $n$ 个点 $m$ 条边。

从第二行开始的之后 $m$ 行，每行四个整数 si s_i 、ti、ci、wi w_i 表示一条从 si s_i 到 ti​ 的边，容量为 ci c_i ​，单位流量需要支付的费用为 wi。

输出格式

一行两个整数，分别表示最大流和最大流需要支付的最小费用。

样例

样例输入

8 232 3 2147483647 11 3 1 12 4 2147483647 21 4 1 22 8 2 03 5 2147483647 31 5 1 33 6 2147483647 41 6 1 43 8 2 03 2 2147483647 04 6 2147483647 51 6 1 54 7 2147483647 61 7 1 64 8 2 04 2 2147483647 05 8 0 05 2 2147483647 06 8 0 06 2 2147483647 07 8 0 07 2 2147483647 0

样例输出

6 24

数据范围与提示

1≤n≤400,0≤m≤15000,wi≥0保证输入数据、中间结果以及答案在 32 位有符号整数范围内。

题目思路

有点像 EK+spfa

AC代码

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn = 5000 + 10;const int maxm = 50000 + 10;const int inf = 0x7fffffff;struct Edge{    int to, w,dist, next;   //可将花费看成距离};Edge e[maxm * 2];int head[maxn];      //用于静态链表int dist[maxn];      //距离int inq[maxn];       //是否在队列中int flow[maxn];   int pre[maxn];int nume[maxn];      //记录边的编号，还可以求反边int cnt;int n, m,s,t,maxflow=0;long long mincost=0;void init(){    for (int i = 0; i <= n; i++) head[i] = -1;    s = 1; t = n;    cnt = 0;}void addedge(int u, int v, int w,int dist){    e[cnt].to = v; e[cnt].w = w; e[cnt].dist = dist;    e[cnt].next = head[u]; head[u]= cnt++;}int spfa(){       queue
         
           q;    for (int i = 0; i <= n; i++) { dist[i] = inf; inq[i] = 0; }    dist[s] = 0;  flow[s] = inf;    q.push(s); inq[s] = 1;    while (!q.empty()){        int p = q.front(); q.pop();inq[p] = 0;        for (int i = head[p]; ~i; i = e[i].next){            int v = e[i].to;            if (e[i].w > 0 && dist[v] > dist[p] + e[i].dist){                dist[v] = dist[p] + e[i].dist;            //更新最短路（花费的角度）                pre[v] = p;                               //记录路径                nume[v] = i;                              //记录这个顶点的编号，i^1就是反向边                flow[v] = min(flow[p],e[i].w);            //更新可行流                if (!inq[v]){ q.push(v); inq[v] = 1; }            }        }    }    return dist[t] < inf;}void MCMF(){   //mcmf主体        while (spfa()){     //如果不可增广，算法结束        int p = t;        while (p != s){            e[nume[p]].w -= flow[t];            e[nume[p]^1].w += flow[t];            p = pre[p];        }        maxflow += flow[t];        mincost += 1ll*flow[t] * dist[t];    }}int main(){    cin >> n >> m ;    int a, b, c, d;    init();    for (int i = 0; i < m; i++){        cin >> a >> b >> c >> d;        addedge(a, b, c, d);        addedge(b, a, 0, -d);    }    MCMF();    cout << maxflow << ' ' << mincost << endl;    return 0;}
         
        
       
      

题解效率