图论
发表算法13 分钟读完 (大约2024个字)

图论

图论算法一般都是揉在一起的，很难单独把算法拆开讲，所以直接上题目吧。分类是大致分的，其实有很多是交叉的。

二叉树

二叉树的遍历有三种，分别为前序遍历，中序遍历和后序遍历，并且给定其中的两种遍历能够求出另一种遍历 (必须已知中序遍历)。

阅读更多
网络流：模板
发表算法 / 网络流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$ 的边视为不存在），那它一定是当前流量下的最小费用，否则一定不是。

阅读更多
关注我

分类

标签

DAG1
DFS3
GitHub1
Hexo1
LCA1
SSH1
STL1
二分图2
动态规划3
匹配2
单调队列2
博客1
双指针1
图书馆3
图论4
小说7
尺取法1
平衡树1
排序1
数据结构1
数论3
最小割1
最短路4
树1
游记1
算法21
网络流5
记忆化搜索4
部署1

最新文章

归档

×