Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

费用流模板

发表于 分类于
本文字数： 4.3k 阅读时长 ≈ 4 分钟
标签：        

dinic/spfa 与 ek/dijkstra（即 Primal-Dual 原始对偶算法）。复杂度与流量和找增广路的复杂度成线性关系。

最大费用只需将最短路都换成最长路即可。

查看代码 
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
73
74
75
76
77
78
79
80
81
82
bool vis[N];
int n, m, st, ed, d[N], cur[N];
int idx = -1, hd[N], nxt[M], edg[M], wt[M], cst[M];
bool bfs()
{
    for (int i = 1; i <= n; i++)
        d[i] = inf;
    d[st] = 0;
    cur[st] = hd[st];
    queue<int> q;
    q.push(st);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        vis[t] = false;
        for (int i = hd[t]; ~i; i = nxt[i])
            if (d[t] + cst[i] < d[edg[i]] && wt[i])
            {
                d[edg[i]] = d[t] + cst[i];
                cur[edg[i]] = hd[edg[i]];
                if (!vis[edg[i]])
                {
                    q.push(edg[i]);
                    vis[edg[i]] = true;
                }
            }
    }
    return d[ed] != inf;
}
int exploit(int x, int limit)
{
    if (x == ed)
        return limit;
    int res = 0;
    vis[x] = true;
    for (int i = cur[x]; ~i && res < limit; i = nxt[i])
    {
        cur[x] = i;
        if (d[edg[i]] == d[x] + cst[i] && wt[i] && !vis[edg[i]])
        {
            int t = exploit(edg[i], min(limit - res, wt[i]));
            if (!t)
                d[edg[i]] = inf;
            res += t;
            wt[i] -= t;
            wt[i ^ 1] += t;
        }
    }
    vis[x] = false;
    return res;
}
int dinic()
{
    int res = 0, flow;
    while (bfs())
        while (flow = exploit(st, inf))
            res += flow * d[ed];
    return res;
}
void add(int a, int b, int c, int d)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
    wt[idx] = c;
    cst[idx] = d;
}
int main()
{
    scanf("%d%d%d%d", &n, &m, &st, &ed);
    for (int i = 1; i <= n; i++)
        hd[i] = -1;
    for (int a, b, c, d; m; m--)
    {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        add(a, b, c, d);
        add(b, a, 0, -d);
    }
    printf("%d", dinic());
    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
73
74
75
76
77
78
typedef pair<int, int> PII;
bool vis[N];
int n, m, st, ed, h[N], d[N], pre[N];
int idx = -1, hd[N], nxt[M], edg[M], wt[M], cst[M];
void add(int a, int b, int c, int d)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
    wt[idx] = c;
    cst[idx] = d;
}
void spfa()
{
    for (int i = 1; i <= n; i++)
        h[i] = inf;
    queue<int> q;
    q.push(st);
    h[st] = 0;
    vis[st] = true;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        vis[t] = false;
        for (int i = hd[t]; ~i; i = nxt[i])
            if (wt[i] && h[t] + cst[i] < h[edg[i]])
            {
                h[edg[i]] = h[t] + cst[i];
                if (!vis[edg[i]])
                {
                    vis[edg[i]] = true;
                    q.push(edg[i]);
                }
            }
    }
}
bool dijkstra()
{
    for (int i = 1; i <= n; i++)
        vis[i] = false, d[i] = inf;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    d[st] = 0;
    q.push(make_pair(0, st));
    while (!q.empty())
    {
        int t = q.top().second;
        q.pop();
        if (vis[t])
            continue;
        vis[t] = true;
        for (int i = hd[t]; ~i; i = nxt[i])
            if (wt[i] && d[t] + cst[i] + h[t] - h[edg[i]] < d[edg[i]])
            {
                d[edg[i]] = d[t] + cst[i] + h[t] - h[edg[i]];
                pre[edg[i]] = i;
                q.push(make_pair(d[edg[i]], edg[i]));
            }
    }
    return d[ed] ^ inf;
}
int PrimalDual ()
{
    spfa();
    int res = 0;
    while (dijkstra())
    {
        for (int i = 1; i <= n; i++)
            h[i] += d[i];
        int t = inf;
        for (int i = ed; i ^ st; i = edg[pre[i] ^ 1])
            t = min(t, wt[pre[i]]);
        for (int i = ed; i ^ st; i = edg[pre[i] ^ 1])
            wt[pre[i]] -= t, wt[pre[i] ^ 1] += t;
        res += t * h[ed];
    }
    return res;
}
相关文章