图论模板——费用流（无法处理负环）

费用流 https://www.acwing.com/problem/content/2176/

//最大流的最小费用
#include<bits/stdc++.h>
using namespace std;

const int N = 5010, M = 100010, INF = 1e8;

int n,m,S,T;
int ne[M],e[M],f[M],w[M],h[N],idx;
int q[N],d[N],pre[N],incf[N];
bool st[N];

void add(int a,int b,int c,int d)
{
    e[idx] = b,ne[idx] = h[a],f[idx] = c,w[idx] = d,h[a] = idx++;
    e[idx] = a,ne[idx] = h[b],f[idx] = 0,w[idx] = -d,h[b] = idx++;
}
bool spfa()
{
    int hh = 0,tt = 1;
    memset(d,0x3f,sizeof d);
    memset(incf,0,sizeof incf);
    q[0] = S,d[S] = 0,incf[S] = INF;
    while (hh!=tt)
    {
        int t = q[hh++];
        if (hh==N) hh = 0;
        st[t] = false;
        for (int i = h[t];i!=-1;i = ne[i])
        {
            int ver = e[i];
            if (f[i] && d[ver] > d[t]+w[i])//这边控制最小费用
            {
                d[ver] = d[t]+w[i];
                pre[ver] = i;
                incf[ver] = min(f[i],incf[t]);
                if (!st[ver])
                {
                    q[tt++] = ver;
                    if (tt==N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T]>0;
}
void EK(int &flow,int &cost)
{
    flow = 0,cost = 0;
    while (spfa())
    {
        int t = incf[T];//t是流量
        flow+=t,cost+=t*d[T];
        for (int i = T;i!=S;i = e[pre[i]^1])
            f[pre[i]] -= t,f[pre[i]^1] += t;
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&S,&T);
    memset(h,-1,sizeof h);
    while (m--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        add(a,b,c,d);
    }
    int flow,cost;
    EK(flow,cost);
    printf("%d %d\n",flow,cost);
    return 0;
}
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