涉江
发表小说 & 随笔 / 陌上4 分钟读完 (大约625个字)

涉江

  E 座的尽头是一扇窗。她喜欢伏在那里的窗棂上，很多个课间。窗外是一幢天井；三面环楼，夐不见曦。

  天井的中央是一台鱼池。一到每年新生入学的时候，鱼们便如笋般冒了出来，流水潺潺，清荣峻茂；整个学校也像鱼池一样变得活络了起来。人们的脸上总是挂着笑容；鱼池旁也缀上了很多人影，来来往往的。

阅读更多
还在用 STL 排序？
发表算法3 分钟读完 (大约495个字)

还在用 STL 排序？

使用 C 库函数

很多人都不知道的是，其实 C 语言也是自带排序函数的，就是位于 <stdlib.h> 库中的 qsort

函数声明：

阅读更多
网络流：最大流
发表算法 / 网络流8 分钟读完 (大约1169个字)

网络流：最大流

EK

增广路方法是很多网络流算法的基础。其思路是每次找出一条从源到汇的能够增加流的路径，调整流值和残留网络 ，直到没有增广路为止。

EK 算法就是不断的找最短路，找的方法就是每次找一条边数最少的增广（即最短路径增广）。

最多要增广多少次？

可以证明，最多 O(VE)​ 次增广，可以达到最大流。

如何找到一条增广路？

先明确什么是增广路。增广路是一条从s到t的路径，路径上每条边残留容量都为正。把残留容量为正的边设为可行的边，那么我们就可以用简单的 BFS 得到边数最少的增广路。

阅读更多
网络流：最小割
发表算法 / 网络流18 分钟读完 (大约2681个字)

网络流：最小割

将图 $G$ 分为 $A$ 和 $B$ 两个点集，$A$ 和 $B$ 之间的边的集合称为无向图的割集。带权图的割 (Cut) 就是割集中的边权之和。

S - T 最小割

特别地，对于一个网络，在满足 $源点 s \in 点集{S}, 汇点 t \in 点集{T}(S\cap T= \varnothing)$ 的情况下，从 S 到 T 的边的权值和被称为 S 到 T 的割。

阅读更多
CF387D
发表算法5 分钟读完 (大约705个字)

CF387D

题意分析

操作最少的次数，构成有趣图，注意无重边，有向边。

  • 操作分为加边和删边。
  • 有趣图定义
    • 有一个中心，满足此点有自环，且与其他结点有双向边。
    • 除中心点外的结点，满足出度 = 入度 = 2。
阅读更多
匹配：模板
发表算法5 分钟读完 (大约715个字)

匹配：模板

UOJ78 二分图最大匹配（DFS - KM）

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
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

const int N = 550;

int match[N], g[N][N], vis[N], link[N];
int n, m, e, tag, ans = 0;

bool dfs(int u) {
    
    for(int v=1; v<=m; ++v) {
        if(!g[u][v] or vis[v] == tag) continue;
        vis[v] = tag;
        if(!match[v] or dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}
int main() {
    
    scanf("%d%d%d", &n, &m, &e);
    for(int i=1, u, v; i<=e; ++i) {
        scanf("%d%d", &u, &v);
        g[u][v] = true;
    }
    
    for(int i=1; i<=n; ++i) {
        tag = i;
        if(dfs(i)) ++ans;
    }
    
    printf("%d\n", ans);
    for(int i=1; i<=m; ++i) link[match[i]] = i;
    
    for(int i=1; i<=n; ++i) printf("%d ", link[i]);
    
    return 0;
}

UOJ79 一般图最大匹配（带花树）

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 550;
int fa[N], match[N], pre[N], vis[N];
int tag = 0, n, m, ans = 0;
int flag[N];
bool g[N][N];
queue<int> q;

void clear(queue<int> &q) {
    queue<int> empty;
    swap(q, empty);
}
int belong(int u) {
    return fa[u] == u ? u : fa[u] = belong(fa[u]);
}

void path(int u) {
    while(u) {
        int v = match[pre[u]];
        match[u] = pre[u];
        match[pre[u]] = u;
        u = v;
    }
}
int lca(int u, int v) {
    ++tag;
    u = belong(u);
    v = belong(v);
    while(vis[u] != tag) {
        vis[u] = tag;
        u = belong(pre[match[u]]);
        if(v) swap(u, v);
    }
    return u;
}
void connect(int u, int v, int root) {
    while(belong(u) != root) {
        pre[u] = v;
        v = match[u];
        if(flag[v] == 2) {
            q.push(v);
            flag[v] = 1;
        }
        if(belong(u) == u) fa[u] = root;
        if(belong(v) == v) fa[v] = root;
        u = pre[v];
    }
}
bool bfs(int u) {
    
    memset(flag, 0, sizeof flag);
    memset(pre, 0, sizeof pre);
    for(int i=1; i<=n; ++i) fa[i] = i;
    
    clear(q);
    q.push(u);
    flag[u] = 1;
    
    while(!q.empty()) {
        u = q.front();
        q.pop();
        for(int v=1; v<=n; ++v) {
            if(!g[u][v]) continue;
            if(flag[v] == 0) {
                pre[v] = u;
                if(match[v] == 0) {
                    path(v);
                    return true;
                }
                q.push(match[v]);
                flag[v] = 2;
                flag[match[v]] = 1;
            } else {
                if(flag[v] == 2) continue;
                if(belong(u) == belong(v)) continue;
                int root = lca(u, v);
                connect(u, v, root);
                connect(v, u, root);
            }
        }
    }
    return false;
}
int main() {
    
    scanf("%d%d", &n, &m);
    for(int i=1, u, v; i<=m; ++i) {
        scanf("%d%d", &u, &v);
        g[u][v] = g[v][u] = true;
    }
    
    for(int i=1; i<=n; ++i) 
        if(match[i] == 0 and bfs(i)) ++ans;
    
    printf("%d\n", ans);
    for(int i=1; i<=n; ++i) printf("%d ", match[i]);
     
    return 0;
}

UOJ80 二分图最大权匹配（BFS - KM）

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
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

typedef long long LL;
const int N = 440;
const LL INF = 0x3f3f3f3f3f3f3f3f;

bool vis[N];
int pre[N], link[N], res[N];
int n, m, e;
LL g[N][N], lx[N], ly[N], d[N], ans = 0;

void bfs(int k) {
    
    int x, y = 0;
    LL min1 = INF, delta;
    memset(vis, false, sizeof vis);
    memset(pre, 0, sizeof pre);
    memset(d, 0x3f, sizeof d);
    link[y] = k;
    
    do {
        x = link[y], delta = INF, vis[y] = true;
        for(int i=1; i<=m; ++i) {
            if(!vis[i]) {
                if(d[i] > lx[x] + ly[i] - g[x][i]) {
                    d[i] = lx[x] + ly[i] - g[x][i];
                    pre[i] = y;
                }
                if(delta > d[i]) delta = d[i], min1 = i;
            }
        }
        for(int i=0; i<=m; ++i)
            if(vis[i]) lx[link[i]] -= delta, ly[i] += delta;
            else d[i] -= delta;
        y = min1;
    } while(link[y]);
    while(y) link[y] = link[pre[y]], y = pre[y];
}

int main() {
    
    scanf("%d%d%d", &n, &m, &e);
    m = max(n, m);
    for(int i=1; i<=e; ++i) {
        int u, v; LL w;
        scanf("%d%d%lld", &u, &v, &w);
        g[u][v] = w;
        lx[u] = max(lx[u], w);
    }
    
    for(int i=1; i<=n; ++i) bfs(i);
    
    for(int i=1; i<=m; ++i) {
        if(!g[link[i]][i]) continue;
        ans += g[link[i]][i];
        res[link[i]] = i;
    }
    printf("%lld\n", ans);
    for(int i=1; i<=n; ++i) printf("%d ", res[i]);
    
    return 0;
}
网络流：模板
发表算法 / 网络流12 分钟读完 (大约1863个字)

网络流：模板

P3376 网络最大流（Dinic）

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 11000, M = 110000;
const int INF = 0x7fffffff;
struct node {
    int u, v, w, next;
} e[M << 1];
int cur[N], h[N], tot;
int dfn[N], ans, n, m, s, t;
void add(int u, int v, int w) {
    e[tot] = node({u, v, w, h[u]});
    cur[u] = h[u] = tot++;
}

bool bfs() {
    memset(dfn, 0, sizeof dfn);
    queue<int> q;
    dfn[s] = 1;
    q.push(s);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = h[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if(e[i].w and !dfn[v]) {
                dfn[v] = dfn[u] + 1;
                q.push(v);
                if(v == t) return true;
            }
        }
    }
    return false;
}
int dfs(int u, int low) {
    if(u == t) return low;
    int w = low;
    for(int i = cur[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        cur[u] = i;
        if(e[i].w and dfn[v] == dfn[u] + 1) {
            int f = dfs(v, min(w, e[i].w));
            e[i].w -= f; e[i^1].w += f;
            w -= f;
            if(!w) break;
        }
    }
    return low - w;
}
void dinic() {
    while(bfs()) {
        memcpy(cur, h, sizeof cur);
        ans += dfs(s, INF);
    }
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(h, -1, sizeof h);
    for(int i=1, u, v, w; i<=m; ++i) {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        add(v, u, 0);
    }
    dinic();
    printf("%d\n", ans);
    return 0;
}

P3381 最小费用最大流（单路增广）

Dijkstra

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
83
84
85
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define il inline

const int N = 5500, M = 55000, INF = 0x3f3f3f3f;

struct point {
    int u, val;
    point(int _u = 0, int _val = 0): u(_u), val(_val) {}
    bool operator < (const point &o) const { return val > o.val; } 
};

priority_queue <point> q;

struct node {
    int u, v, w, f, next;
    node() {}
} e[M << 1];
int head[N], tot = 0;

il void add(int u, int v, int w, int f) {
    e[tot].u = u, e[tot].v = v, e[tot].w = w, e[tot].f = f;
    e[tot].next = head[u]; head[u] = tot++;
}

int h[N], dis[N], flow[N], pre[N];

int n, m, s, t;

int maxflow = 0, mincost = 0;
il bool dijkstra() {
    memset(dis, 0x3f, sizeof dis);
    memset(flow, 0x3f, sizeof flow);
    memset(pre, -1, sizeof pre);
    
    dis[s] = 0;
    q.push(point(s, 0));
    while (!q.empty()) {
        int u = q.top().u, val = q.top().val;
        q.pop();
        if (val > dis[u]) continue;
        for (int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if (e[i].w and dis[v] > dis[u] + e[i].f + h[u] - h[v]) {
                pre[v] = i;
                flow[v] = min(flow[u], e[i].w);
                dis[v] = dis[u] + e[i].f + h[u] - h[v];
                q.push(point(v, dis[v]));
            }
        }
    }
    return dis[t] != INF;
}

il void check() {
    
    for (int p = pre[t]; p != -1; p = pre[e[p].u]) {
        e[p].w -= flow[t];
        e[p^1].w += flow[t];
    }
    maxflow += flow[t];
    mincost += (dis[t] - h[s] + h[t]) * flow[t];
    
    for(int i=1; i<=n; ++i) h[i] += dis[i];
}


int main() {
    
    memset(head, -1, sizeof head);
    
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for(int i=1, u, v, w, f; i<=m; ++i) {
        scanf("%d%d%d%d", &u, &v, &w, &f);
        add(u, v, w, f);
        add(v, u, 0, -f);
    }
    
    while (dijkstra()) check();
    printf("%d %d\n", maxflow, mincost);
    
    return 0;
}

SPFA

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
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 5500, M = 110000, INF = 0x3f3f3f3f;

struct node {
    int u, v, w, f, next;
} e[M];
int h[N], tot = 0;

void add(int u, int v, int w, int f) {
    e[tot] = {u, v, w, f, h[u]};
    h[u] = tot++;
}

int pre[N], flow[N], dis[N];
bool vis[N];

int n, m, s, t, maxflow, mincost;

bool spfa() {
    
    memset(pre, -1, sizeof pre);
    memset(vis, false, sizeof vis);
    memset(dis, 0x3f, sizeof dis);
    memset(flow, 0x3f, sizeof flow);
    
    queue<int> q;
    q.push(s);
    vis[s] = true;
    dis[s] = 0;
    
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = h[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if(e[i].w and dis[v] > dis[u] + e[i].f) {
                dis[v] = dis[u] + e[i].f;
                pre[v] = i;
                flow[v] = min(flow[u], e[i].w);
                if(!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
    
    return dis[t] != INF;
}

void check() {
    for(int p = pre[t]; p != -1; p = pre[e[p].u]) {
        e[p].w -= flow[t];
        e[p^1].w += flow[t];
    }
    
    mincost += dis[t] * flow[t];
    maxflow += flow[t];
}
int main() {
    
    scanf("%d%d%d%d", &n, &m, &s, &t);
    
    memset(h, -1, sizeof h); 
    for(int i=1, u, v, w, f; i<=m; ++i) {
        scanf("%d%d%d%d", &u, &v, &w, &f);
        add(u, v, w, f);
        add(v, u, 0, -f);
    }
    
    while(spfa()) check();
    
    printf("%d %d\n", maxflow, mincost);

    return 0;
}

LOJ115 无源汇有上下界可行流（超级源汇）

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
#define il inline

const int N = 220, M = 11000, INF = 0x3f3f3f3f;

struct node {
    int u, v, w, next;
} e[M * 6];

int head[N], cur[N], tot = 0;

il void add(int u, int v, int w) {
    e[tot] = (node) {u, v, w, head[u]};
    head[u] = tot++;
}

int h[N], n, m, ss, tt;
il bool bfs() { //分层 
    
    memset(h, 0, sizeof h);
    memcpy(cur, head, sizeof cur);
    queue<int> q;
    q.push(ss);
    h[ss] = 1;
    
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u]; i != -1; i = e[i].next) {
            int v = e[i].v;
            if(e[i].w and !h[v]) {
                h[v] = h[u] + 1;
                if(v == tt) return true;
                q.push(v);
            }
        }
    }
    return false;
}

int dfs(int u, int low) {
    if(u == tt) return low;
    int w = low;
    for(int i = cur[u]; i != -1; i = e[i].next, cur[u] = i) {
        int v = e[i].v;
        if(e[i].w and h[v] == h[u] + 1) {
            int f = dfs(v, min(w, e[i].w));
            e[i].w -= f;
            e[i^1].w += f;
            w -= f;
            if(!w) break;
        }
    }
    return low - w;
}

int tflow = 0, sflow = 0;
il void dinic() {
    
    for(int i = head[ss]; i != -1; i = e[i].next)
        sflow += e[i].w; //出流量 
        
    while(bfs()) dfs(ss, INF);
    
    for(int i = head[tt]; i != -1; i = e[i].next) 
        tflow += e[i].w; //入流量 
    
    if(sflow == tflow) { //满流 
        printf("YES\n");
        for(int i=0; i<tot; i+=6) 
            printf("%d\n", e[i+1].w + e[i+5].w); //反边流量和 
    } else printf("NO\n");
    
}
int main() {
    
    freopen("loj115.in", "r", stdin);
    
    scanf("%d%d", &n, &m);
    
    memset(head, -1, sizeof head);
    ss = 0, tt = n+1;
    for(int i=1, u, v, l, h; i<=m; ++i) { //建图 
        scanf("%d%d%d%d", &u, &v, &l, &h);
        add(u, tt, l);
        add(tt, u, 0);
        add(ss, v, l);
        add(v, ss, 0);
        add(u, v, h-l);
        add(v, u, 0);
    }
    
    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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 220, M = 22000, INF = 0x3f3f3f3f;

struct node {
    int u, v, w, next;
} e[M];
int head[N], cur[N], tot = 0;
void add(int u, int v, int w) {
    e[tot] = (node) {u, v, w, head[u]};
    head[u] = tot++;
    e[tot] = (node) {v, u, 0, head[v]};
    head[v] = tot++;
}
int h[N], in[N], n, m, s, t, ss, tt, sflow = 0, tflow = 0;
bool bfs(int s, int t) {
    
    memset(h, 0, sizeof h);
    memcpy(cur, head, sizeof cur);
    
    queue<int> q;
    q.push(s);
    h[s] = 1;
    
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u], v; i != -1; i = e[i].next) {
            v = e[i].v;
            if(e[i].w and !h[v]) {
                h[v] = h[u] + 1;
                if(v == t) return true;
                q.push(v); 
            }
        }
    }
    return false;
}

int dfs(int u, int low, int t) {
    if(u == t) return low;
    
    int w = low;
    for(int i = cur[u], v; i != -1; i = e[i].next, cur[u] = i) {
        v = e[i].v;
        if(e[i].w and h[v] == h[u] + 1) {
            int f = dfs(v, min(w, e[i].w), t);
            e[i].w -= f;
            e[i^1].w += f;
            w -= f;
            if(!w) break;
        }
    }
    return low - w;
}

int main() {
    
    //freopen("loj116.in", "r", stdin);
    
    scanf("%d%d%d%d", &n, &m, &s, &t);
    
    ss = 0, tt = n+1;
    memset(head, -1, sizeof head);
    for(int i=1, u, v, l, h; i<=m; ++i) {
        scanf("%d%d%d%d", &u, &v, &l, &h);
        in[u] -= l; in[v] += l;
        add(u, v, h-l);
    }
    
    for(int i=1; i<=n; ++i) {
        if(!in[i]);
        else if(in[i] > 0) {
            sflow += in[i];
            add(ss, i, in[i]);
        } else {
            add(i, tt, -in[i]);
        }
    }
    
    add(t, s, INF);
    
    while(bfs(ss, tt)) tflow += dfs(ss, INF, tt);
    
    if(sflow != tflow) {
        printf("please go home to sleep\n");
        return 0;
    }
    
    for(int i = head[ss]; i != -1; i = e[i].next) 
        e[i].w = e[i^1].w = 0;
    
    for(int i = head[tt]; i != -1; i = e[i].next)
        e[i].w = e[i^1].w = 0;
    
    int sum = e[--tot].w;
    e[tot-1].w = e[tot].w = 0;
    
    while(bfs(s, t)) sum += dfs(s, INF, t);
    
    printf("%d\n", sum);
        
    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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 220, M = 22000, INF = 0x3f3f3f3f;

struct node {
    int u, v, w, next;
} e[M];
int head[N], cur[N], tot = 0;
void add(int u, int v, int w) {
    e[tot] = (node) {u, v, w, head[u]};
    head[u] = tot++;
    e[tot] = (node) {v, u, 0, head[v]};
    head[v] = tot++;
}
int h[N], in[N], n, m, s, t, ss, tt, sflow = 0, tflow = 0;
bool bfs(int s, int t) {
    
    memset(h, 0, sizeof h);
    memcpy(cur, head, sizeof cur);
    
    queue<int> q;
    q.push(s);
    h[s] = 1;
    
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i = head[u], v; i != -1; i = e[i].next) {
            v = e[i].v;
            if(e[i].w and !h[v]) {
                h[v] = h[u] + 1;
                if(v == t) return true;
                q.push(v); 
            }
        }
    }
    return false;
}

int dfs(int u, int low, int t) {
    if(u == t) return low;
    
    int w = low;
    for(int i = cur[u], v; i != -1; i = e[i].next, cur[u] = i) {
        v = e[i].v;
        if(e[i].w and h[v] == h[u] + 1) {
            int f = dfs(v, min(w, e[i].w), t);
            e[i].w -= f;
            e[i^1].w += f;
            w -= f;
            if(!w) break;
        }
    }
    return low - w;
}

int main() {
    
    //freopen("loj116.in", "r", stdin);
    
    scanf("%d%d%d%d", &n, &m, &s, &t);
    
    ss = 0, tt = n+1;
    memset(head, -1, sizeof head);
    for(int i=1, u, v, l, h; i<=m; ++i) {
        scanf("%d%d%d%d", &u, &v, &l, &h);
        in[u] -= l; in[v] += l;
        add(u, v, h-l);
    }
    
    for(int i=1; i<=n; ++i) {
        if(!in[i]);
        else if(in[i] > 0) {
            sflow += in[i];
            add(ss, i, in[i]);
        } else {
            add(i, tt, -in[i]);
        }
    }
    
    add(t, s, INF);
    
    while(bfs(ss, tt)) tflow += dfs(ss, INF, tt);
    
    if(sflow != tflow) {
        printf("please go home to sleep\n");
        return 0;
    }
    
    for(int i = head[ss]; i != -1; i = e[i].next) 
        e[i].w = e[i^1].w = 0;
    
    for(int i = head[tt]; i != -1; i = e[i].next)
        e[i].w = e[i^1].w = 0;
    
    int sum = e[--tot].w;
    e[tot-1].w = e[tot].w = 0;
    
    while(bfs(s, t)) sum += dfs(s, INF, t);
    
    printf("%d\n", sum);
        
    return 0;
}
网络流：Dijkstra 求费用流
发表算法 / 网络流5 分钟读完 (大约737个字)

网络流：Dijkstra 求费用流

注：下文中的边权 $w$ 均表示费用 $f$。

Dijkstra 不能求有负权边的最短路，所以我们可以对网络 $G$ 中的每一个点设置一个势函数 $h(u)$，以满足在与原图等价的新图中的边权非负。

阅读更多
网络流：消圈算法
发表算法 / 网络流9 分钟读完 (大约1278个字)

网络流：消圈算法

注：下文中的权均表示费用。

消圈定理

在某个流 $f$ 中，如果其残余网络中没有负圈（剩余流量为 $0$ 的边视为不存在），那它一定是当前流量下的最小费用，否则一定不是。

阅读更多
陌上
发表小说 & 随笔 / 陌上3 分钟读完 (大约468个字)

陌上

  多少次咫尺之隔的希望

  却终是目送着的离开

  最美好的时候（）

  ？

阅读更多
关注我

分类

标签

AI3
Aplayer1
Butterfly1
DAG1
DFS3
GitHub1
Gulp1
Hexo4
LCA1
PB_DS1
PWA1
SSH1
STL2
Vercel1
二分图2
动态规划3
匹配2
单调队列2
博客4
双指针1
图书馆4
图论4
小说7
尺取法1
平衡树1
应用程序1
排序2
数学2
数据结构1
数论3
最小割1
最短路4
树1
游记1
码风1
算法26
网络流5
记忆化搜索4
部署3
随感1
随笔1

最新文章

归档

×