网络流：模板
发表算法 / 网络流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;
}
网络流：消圈算法
发表算法 / 网络流9 分钟读完 (大约1278个字)

网络流：消圈算法

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

消圈定理

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

阅读更多
网络流：Dijkstra 求费用流
发表算法 / 网络流5 分钟读完 (大约737个字)

网络流：Dijkstra 求费用流

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

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

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

陌上

  多少次咫尺之隔的希望

  却终是目送着的离开

  最美好的时候（）

  ？

阅读更多
尺取法
发表算法17 分钟读完 (大约2596个字)

尺取法

尺取法，又称滑动窗口或双指针，是一种在序列上寻找最优解的方法．对于序列的每个左端点 $l$，让右端点 $r$ 尽可能延伸至最远，得到一个答案区间，$r$ 已到达最远后将与 $l$ 有关的信息弹出，对于多个答案区间找出最优解．复杂度通常为线性．

不过一些时候这样不能保证求得的是最优解，这时就需要其他思路，或者使用莫队（根号算法）暴力求解．

阅读更多
单调队列
发表算法6 分钟读完 (大约875个字)

单调队列

单调队列是一种特殊维护的队列。一般地，当一新值准备入队时，须先从后向前，将对后来答案没有了影响的点弹出，再从前向后，将所有超出了统计范围的点弹出。对于大多数问题，求解过程中会锁定很多答案区间，在线求最值。

阅读更多
About CODESTYLE
发表算法3 分钟读完 (大约493个字)

About CODESTYLE

Commit 命名规范

  • feat: 一个新功能
  • fix: 一个 bug 修复
  • docs: 仅仅修改了文档，比如 README, CHANGELOG, CONTRIBUTE 等
  • style: 不影响代码逻辑的修改，比如空格、格式缩进、删除分号等
  • refactor: 代码重构
  • perf: 提升性能的改动
  • test: 增加或修改测试
  • chore: 改变构建流程、或者增加辅助工具、依赖库等
阅读更多
发表小说 & 随笔4 分钟读完 (大约611个字)

雪（精选集）

连载小说 & 概念 EP & 随笔

系列一：连载小说

（主线剧情：星, 梦, 昙 → 未来 → 黎明之烬 → 涉江 & 凝眉）

最新：凝眉

纪念初中时候的一段故事吧。顺便把这个系列收个尾。大概就结束了。

他和她坐在跑道边，说是要等着，等最后一片云霞沉寂在地平线下。时不时地，他们凑在对方的耳边，轻声低语；欢谑声里，沉沉的烟火灿烂着，像雪染成的白绫。风打在他和她的肩上。

阅读更多
浅谈 Splay（一）
发表算法7 分钟读完 (大约1071个字)

浅谈 Splay（一）

1. 右旋（Right Rotation）

观察每个节点的变化，其中每个节点都有指向其父节点的指针没有画出。

1.png

①②③处节点连接有变化。

阅读更多
未来
发表小说 & 随笔 / 未来22 分钟读完 (大约3347个字)

未来

“When you have that last piece of the jigsaw, everything will, I hope, be clear. . . ."

「引子」

我听着《我们仍不知道那年中美合拍的日子》，突然，章老师走了进来。我打开空气净化器，看了看垃圾桶里闪闪发光的律师函。

总之，故事就这样开始了。

阅读更多
关注我

分类

标签

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

最新文章

归档

×