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

网络流：消圈算法

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

消圈定理

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

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

网络流：Dijkstra 求费用流

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

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

阅读更多
尺取法
发表算法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: 改变构建流程、或者增加辅助工具、依赖库等
阅读更多
关注我

分类

标签

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

最新文章

归档

×