Chaos Slover 补档计划 - 网络流经典变形与模型

2015.11.24 10:17 Tue| 1 visits oi_2016| ChaosSlover补档计划| Text

这几天开的新坑有点多啊,而且还开了这么大的一个坑……做两道 CDQ 分治做两道网络流这样子真的好么……

最大权闭合图

对于正权点 u,从 S 到 u 连一条容量为点权的边;对于负权点 v,从 v 到 T 连一条容量为点权相反数的边;对于原图中的边 u→v,从 u 到 v 连一条容量为无穷的边。

则答案为(正点权之和-最小割)。

JDFZOJ2489 太空飞行计划问题

经典例题。然而这个题的读入输出是会死人的!

  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
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define N 105
#define M 10005

int n, m, s, t, sum, head[N], d[N], v[N];

inline int read()
{
    static char ch;
    int x = 0;
    if (ch == '\n') { ch = 0; return -1; }
    ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '\n') return -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x;
}

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

queue<int> q;

bool bfs()
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

int dfs(int x, int f)
{
    if (x == t) return f;
    int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            int k = dfs(edge[i].to, min(temp, edge[i].val));
            if (k == 0) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

int dinic()
{
    int re = 0;
    while (bfs())
        re += dfs(s, inf);
    return re;
}

void getans(int x)
{
    v[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && !v[edge[i].to])
            getans(edge[i].to);
}

int main()
{
    while ((n = read()) == -1);
    m = read();
    s = 0; t = n + m + 1;
    for (int x, i = 1; i <= n; ++i)
    {
        while ((x = read()) == -1);
        add(s, i, x), add(i, s, 0);
        sum += x;
        while ((x = read()) != -1)
            add(i, n + x, inf), add(n + x, i, 0);
    }
    for (int x, i = 1; i <= m; ++i)
    {
        while ((x = read()) == -1);
        add(n + i, t, x), add(t, n + i, 0);
    }
    int ans = dinic();
    getans(s);
    while (!q.empty()) q.pop();
    for (int i = 1; i <= n; ++i)
        if (v[i]) q.push(i);
    while (!q.empty())
        printf("%d%c", q.front(), q.size() == 1 ? '\n' : ' '), q.pop();
    for (int i = 1; i <= m; ++i)
        if (v[n + i]) q.push(i);
    while (!q.empty())
        printf("%d%c", q.front(), q.size() == 1 ? '\n' : ' '), q.pop();
    printf("%d\n", sum - ans);
    return 0;
}

[NOI2006]最大获利

最大权闭合图的裸题。大概是二分图,然而边数和点数都好大啊——网络流的时间复杂度还真是远远小于上界呢。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 55005
#define M 400005
#define inf 0x3f3f3f3f

int n, m, s, t, ans, head[N], d[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, int z)
{
    static int cnt = 1;
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

queue<int> q;

bool bfs()
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

int dfs(int x, int f)
{
    if (x == t) return f;
    int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            int k = dfs(edge[i].to, min(edge[i].val, temp));
            if (k == 0) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

int dinic()
{
    int re = 0;
    while (bfs()) re += dfs(s, inf);
    return re;
}

int main()
{
    n = read(); m = read();
    t = n + m + 1;
    for (int i = 1; i <= n; ++i)
        add(m + i, t, read()), add(t, m + i, 0);
    for (int x, i = 1; i <= m; ++i)
    {
        add(i, m + (x = read()), inf), add(m + x, i, 0);
        add(i, m + (x = read()), inf), add(m + x, i, 0);
        add(s, i, x = read()), add(i, s, 0); ans += x;
    }
    cout << ans - dinic() << endl;
    return 0;
}

最大密度子图

运用 01 分数规划二分答案。假设边数与点数的最大比值为 g,那么最优值出现在 |E|-g*|V|=0 时。如果左式的最大取值小于 0,那么应减小 g,否则应增加 g。设 h(g)=max{|E|-g*|V|},那么我们就可以通过网络流求出函数 h 的取值了。

这里存在两种解法:

解法 1

将边也看作是点。每一条边都依赖于两个点。设边的权值为 1,点的权值为 -g,就可以将原题转化为最大权闭合图模型了。

注意此时求出的函数 h 的取值不可能小于 0,那么我们需要求的就是使得函数 h 的取值不为 0 的最大的 g。

这种做法的点数为 n+m+2,边数为 2n+6m。

解法 2

原点向各个点连接一条权值为 U 的有向边(U 为定值,使得 U+2*g-d 恒为正,可取值为 m),各个点向汇点连一条权值为 U+2*g-d 的有向边,其中 d 为这个点的出度。原来的图中每一条边的两端点间两个方向各连一条权值为 1 的有向边,然后函数 h 的取值就是 (U*n-mincut())/2。证明什么的好大一坨啊……我决定不去看了。

向点边均带权的图的推广

定义点边均带权的无向图的密度为该图的点权和加上边权和的和与该图的点数的比值。此时函数 h 就变成了 max{sum(w)-(g*|V|-sum(p))}。

原点到各个点连接一条权值为 U 的有向边(U 可取值为 2*sum(abs(p))+sum(w)),各个点到汇点连一条权值为 U+2*g-d-2p 的有向边,d 的含义是当前点的出边的边权和。原来的图中每一条边的两端点间两个方向各连一条权值为 w 的有向边,然后函数 h 的取值还是 (U*n-mincut())/2。

POJ3155 Hard Life

需要输出方案。本题十分卡精度。据论文证明,不同解之间误差的精度不超过 1 / (n * n)。跑最大流的时候,可以将边权的精度设为 1e-8。

解法1

  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
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

#define eps 1e-8
#define inf 1e8

#define N 1500
#define M 10000

int n, m, s, t, a[N], b[N], head[N], d[N], v[N], cnt;
queue<int> q;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to; double val;
    graph() {}
    graph(int _next, int _to, double _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, double z)
{
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

bool bfs()
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    q.push(s); d[s] = 1;
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val > eps && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

double dfs(int x, double f)
{
    if (x == t) return f;
    double temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val > eps && d[edge[i].to] == d[x] + 1)
        {
            double k = dfs(edge[i].to, min(temp, edge[i].val));
            if (k < eps) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if ((temp -= k) < eps) break;
        }
    return f - temp;
}

double dinic()
{
    double re = 0;
    while (bfs()) re += dfs(s, inf);
    return re;
}

void build(double g)
{
    memset(head, 0, sizeof head);
    cnt = 1;
    for (int i = 1; i <= m; ++i)
        add(s, i, 1), add(i, s, 0);
    for (int i = 1; i <= n; ++i)
        add(m + i, t, g), add(t, m + i, 0);
    for (int i = 1; i <= m; ++i)
        add(i, m + a[i], inf), add(m + a[i], i, 0),
        add(i, m + b[i], inf), add(m + b[i], i, 0);
}

void getans(int x)
{
    v[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (!v[edge[i].to] && edge[i].val > 0)
            getans(edge[i].to);
}

int main()
{
    n = read(), m = read();
    if (m == 0) { printf("1\n1\n"); return 0; }
    s = 0; t = n + m + 1;
    for (int i = 1; i <= m; ++i)
        a[i] = read(), b[i] = read();
    double l = 0, r = m;
    while (r - l > 1.0 / n / n)
    {
        double mid = (l + r) / 2;
        build(mid);
        if (m - dinic() < eps) r = mid;
        else l = mid;
    }
    int ans = 0;
    build(l); dinic(); getans(s);
    for (int i = 1; i <= n; ++i)
        if (v[m + i])  ++ans;
    cout << ans << endl;
    for (int i = 1; i <= n; ++i)
        if (v[m + i])  printf("%d\n", i);
    return 0;
}

解法2

  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
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
using namespace std;

#define eps 1e-8
#define inf 1e8

#define N 150
#define M 5000

int n, m, s, t, a[1005], b[1005], head[N], d[N], v[N], out[N], cnt;
queue<int> q;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to; double val;
    graph() {}
    graph(int _next, int _to, double _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, double z)
{
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

bool bfs()
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    q.push(s); d[s] = 1;
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val > eps && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

double dfs(int x, double f)
{
    if (x == t) return f;
    double temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val > eps && d[edge[i].to] == d[x] + 1)
        {
            double k = dfs(edge[i].to, min(temp, edge[i].val));
            if (k < eps) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if ((temp -= k) < eps) break;
        }
    return f - temp;
}

double dinic()
{
    double re = 0;
    while (bfs()) re += dfs(s, inf);
    return re;
}

void build(double g)
{
    memset(head, 0, sizeof head);
    cnt = 1;
    for (int i = 1; i <= n; ++i)
        add(s, i, m), add(i, s, 0),
        add(i, t, m + 2 * g - out[i]), add(t, i, 0);
    for (int i = 1; i <= m; ++i)
        add(a[i], b[i], 1), add(b[i], a[i], 1);
}

void getans(int x)
{
    v[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
        if (!v[edge[i].to] && edge[i].val > 0)
            getans(edge[i].to);
}

int main()
{
    n = read(), m = read();
    if (m == 0) { printf("1\n1\n"); return 0; }
    s = 0; t = n + 1;
    for (int i = 1; i <= m; ++i)
        a[i] = read(), b[i] = read(), ++out[a[i]], ++out[b[i]];
    double l = 0, r = m;
    while (r - l > 1.0 / n / n)
    {
        double mid = (l + r) / 2;
        build(mid);
        if ((m * n - dinic()) / 2 < eps) r = mid;
        else l = mid;
    }
    int ans = 0;
    build(l); dinic(); getans(s);
    for (int i = 1; i <= n; ++i)
        if (v[i])  ++ans;
    cout << ans << endl;
    for (int i = 1; i <= n; ++i)
        if (v[i])  printf("%d\n", i);
    return 0;
}

[NOI2006]最大获利

将用户群看成边,中转站看成点。然后跑最大密度子图。代码实现就先挖坑吧~

有上下界的网络流问题

无源汇有上下界可行流

SGU194 Reactor Cooling

 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 <bits/stdc++.h>
using namespace std;

#define N 205
#define M 200000
#define inf 0x3f3f3f3f

int n, m, du[N], p[M], pos[M], sum;
int s, t, head[N], cnt = 1, d[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, int z)
{
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
    edge[++cnt] = graph(head[y], x, 0);
    head[y] = cnt;
}

queue<int> q;

bool bfs()
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

int dfs(int x, int f)
{
    if (x == t) return f;
    int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            int k = dfs(edge[i].to, min(temp, edge[i].val));
            if (k == 0) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

int dinic()
{
    int re = 0;
    while (bfs())
        re += dfs(s, inf);
    return re;
}


int main()
{
    cin >> n >> m;
    s = 0; t = n + 1;
    for (int x, y, q, i = 1; i <= m; ++i)
    {
        x = read(), y = read(), p[i] = read(), q = read();
        add(x, y, q - p[i]); du[x] -= p[i]; du[y] += p[i]; pos[i] = cnt;
    }
    for (int i = 1; i <= n; ++i)
        if (du[i] > 0)
            add(s, i, du[i]), sum += du[i];
        else if (du[i] < 0)
            add(i, t, -du[i]);
    if (dinic() != sum) { puts("NO"); return 0; }
    puts("YES");
    for (int i = 1; i <= m; ++i)
        printf("%d\n", p[i] + edge[pos[i]].val);
    return 0;
}

POJ2396&ZOJ1994 Budget

给出一个矩阵每一行的和与每一列的和,并给出每个格子的上下界,求出一个合法的矩阵。

将行、列看作点,可以转化成有上下界的最大流模型。将行和列分别连到原点和汇点,并将上下界均设成相应的和。这样就可以保证如果存在可行流,就一定会存在合法的解。其实对于这一道题而言,求出一组可行解也就可以了,因为可行解一定会和最大流是相等的,直接输出答案 mat[i][j]=mint[i][j]+edge(j→i).val 即可。当然再求一遍最大流也不会有任何问题。

ZOJ 最后一行有空行会 WA。

  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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <bits/stdc++.h>
using namespace std;

#define N 250
#define inf 0x3f3f3f3f

int m, n, p, sum1, sum2, r[N], c[N], mint[N][N], maxt[N][N];
int s, t, ss, tt, ans, cnt, sum, head[N], d[N], pos[N][N];
queue<int> q;

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[20000];

inline void add(int x, int y, int z)
{
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
}

bool bfs(int s, int t)
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

int dfs(int x, int f, int t)
{
    if (x == t) return f;
    int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            int k = dfs(edge[i].to, min(temp, edge[i].val), t);
            if (!k) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

int dinic(int s, int t)
{
    int re = 0;
    while (bfs(s, t))
        re += dfs(s, inf, t);
    return re;
}

void init()
{
    memset(head, 0, sizeof head); cnt = 1;
    memset(mint, 0, sizeof mint);
    memset(maxt, 0x3f, sizeof maxt);
    sum1 = sum2 = sum = 0;
}

int main()
{
    int test;
    cin >> test;
    while (test--)
    {
        init();
        cin >> m >> n;
        for (int i = 1; i <= m; ++i)
            cin >> r[i], sum1 += r[i];
        for (int i = 1; i <= n; ++i)
            cin >> c[i], sum2 += c[i];
        cin >> p;
        char str[5];
        for (int x, y, z, i = 1; i <= p; ++i)
        {
            scanf("%d%d%s%d", &x, &y, str, &z);
            int u = x, d = x, l = y, r = y;
            if (x == 0) u = 1, d = m;
            if (y == 0) l = 1, r = n;
            for (int j = u; j <= d; ++j)
                for (int k = l; k <= r; ++k)
                    if (str[0] == '=')
                        mint[j][k] = max(mint[j][k], z),
                        maxt[j][k] = min(maxt[j][k], z);
                    else if (str[0] == '<')
                        maxt[j][k] = min(maxt[j][k], z - 1);
                    else
                        mint[j][k] = max(mint[j][k], z + 1);
        }
        if (sum1 != sum2) goto end;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                if (mint[i][j] > maxt[i][j])
                    goto end;
        s = 0; t = n + m + 1; ss = t + 1; tt = ss + 1;
        for (int i = 1; i <= m; ++i)
        {
            int temp = r[i];
            for (int j = 1; j <= n; ++j)
                temp -= mint[i][j];
            if (temp > 0) sum += temp, add(ss, i, temp), add(i, ss, 0);
            else if (temp < 0) add(i, tt, -temp), add(tt, i, 0);
        }
        for (int i = 1; i <= n; ++i)
        {
            int temp = -c[i];
            for (int j = 1; j <= m; ++j)
                temp += mint[j][i];
            if (temp > 0) sum += temp, add(ss, m + i, temp), add(m + i, ss, 0);
            else if (temp < 0) add(m + i, tt, -temp), add(tt, m + i, 0);
        }
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                add(i, m + j, maxt[i][j] - mint[i][j]),
                add(m + j, i, 0), pos[i][j] = cnt;
        sum += sum2;
        add(s, tt, sum1); add(tt, s, 0); add(ss, t, sum2); add(t, ss, 0);
        add(t, s, inf); add(s, t, 0);
        ans = dinic(ss, tt);
        if (ans == sum)
        {
            head[t] = edge[head[t]].next;
            head[s] = edge[head[s]].next;
            dinic(s, t);
            for (int i = 1; i <= m; ++i)
                for (int j = 1; j <= n; ++j)
                    printf("%d%c", mint[i][j] + edge[pos[i][j]].val,
                                   " \n"[j == n]);
            if (test) puts("");
            continue;
        }
        end: puts("IMPOSSIBLE");
        if (test) puts("");
    }
    return 0;
}

有源汇有上下界最大流

ZOJ3229 Shoot the Bullet

这是一道裸题,然而我一直想吐槽 ZOJ 上的 PE 算作是 WA。

  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
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

#define N 2000
#define M 200005
#define inf 0x3f3f3f3f

int n, m, du[N], sum, tot, g[M], pos[M];
int s, t, ss, tt, head[N], cnt = 1, d[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, int z, int w = 0)
{
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
    edge[++cnt] = graph(head[y], x, 0);
    head[y] = cnt; du[x] -= w; du[y] += w;
}

queue<int> q;

bool bfs(int s, int t)
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

int dfs(int x, int f, int t)
{
    if (x == t) return f;
    int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            int k = dfs(edge[i].to, min(temp, edge[i].val), t);
            if (k == 0) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

int dinic(int s, int t)
{
    int re = 0;
    while (bfs(s, t))
        re += dfs(s, inf, t);
    return re;
}

void init()
{
    memset(head, 0, sizeof head); cnt = 1;
    memset(du, 0, sizeof du); sum = 0; tot = 0;
}

int main()
{
    while (cin >> n >> m)
    {
        init();
        s = 0; t = n + m + 1; ss = t + 1; tt = ss + 1;
        for (int i = 1; i <= m; ++i)
            add(n + i, t, inf, read());
        for (int x, y, z, q, i = 1; i <= n; ++i)
        {
            x = read(); y = read();
            add(s, i, y);
            for (int j = 1; j <= x; ++j)
                z = read() + 1, g[++tot] = read(), q = read(),
                add(i, n + z, q - g[tot], g[tot]), pos[tot] = cnt;
        }
        for (int i = s; i <= t; ++i)
            if (du[i] > 0) sum += du[i], add(ss, i, du[i]);
            else if (du[i] < 0) add(i, tt, -du[i]);
        add(t, s, inf);
        if (dinic(ss, tt) == sum)
        {
            head[ss] = head[tt] = 0;
            head[s] = edge[head[s]].next;
            head[t] = edge[head[t]].next;
            cout << sum + dinic(s, t) << endl;
            for (int i = 1; i <= tot; ++i)
            {
                printf("%d\n", g[i] + edge[pos[i]].val);
            }
        }
        else puts("-1");
        puts("");
    }
    return 0;
}

有源汇有上下界最小流

SGU176 Flow construction

先进行一次 Dinic,然后再加入从 t 到 s,容量为无穷的边,再进行一次 Dinic。如果两次 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
 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 <bits/stdc++.h>
using namespace std;

#define N 105
#define M 30005
#define inf 0x3f3f3f3f

int n, m, p[M], du[N], sum, pos[M];
int ss, tt, head[N], cnt = 1, d[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct graph
{
    int next, to, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[M];

inline void add(int x, int y, int z)
{
    edge[++cnt] = graph(head[x], y, z);
    head[x] = cnt;
    edge[++cnt] = graph(head[y], x, 0);
    head[y] = cnt;
}

queue<int> q;

bool bfs(int s, int t)
{
    memset(d, 0, sizeof d);
    while (!q.empty()) q.pop();
    d[s] = 1; q.push(s);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && !d[edge[i].to])
            {
                d[edge[i].to] = d[x] + 1;
                if (edge[i].to == t) return true;
                q.push(edge[i].to);
            }
    }
    return false;
}

int dfs(int x, int f, int t)
{
    if (x == t) return f;
    int temp = f;
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].val && d[edge[i].to] == d[x] + 1)
        {
            int k = dfs(edge[i].to, min(temp, edge[i].val), t);
            if (k == 0) d[edge[i].to] = 0;
            edge[i].val -= k; edge[i ^ 1].val += k;
            if (!(temp -= k)) break;
        }
    return f - temp;
}

int dinic(int s, int t)
{
    int re = 0;
    while (bfs(s, t))
        re += dfs(s, inf, t);
    return re;
}

int main()
{
    cin >> n >> m;
    ss = 0; tt = n + 1;
    for (int x, y, z, c, i = 1; i <= m; ++i)
    {
        x = read(), y = read(), z = read(), c = read();
        if (c) p[i] = z, du[x] -= z, du[y] += z;
        else add(x, y, z), pos[i] = cnt;
    }
    for (int i = 1; i <= n; ++i)
        if (du[i] > 0) sum += du[i], add(ss, i, du[i]);
        else if (du[i] < 0) add(i, tt, -du[i]);
    int ans = dinic(ss, tt);
    add(n, 1, inf);
    ans += dinic(ss, tt);
    if (ans == sum)
    {
        cout << edge[head[1]].val << endl;
        for (int i = 1; i <= m; ++i)
            if (p[i]) printf("%d ", p[i]);
            else printf("%d ", edge[pos[i]].val);
    }
    else puts("Impossible");
    return 0;
}