Chaos Slover 补档计划 - 网络流相关题目与应用(1 最大流)

2015.11.25 10:26 Wed| 1 visits oi_2016| ChaosSlover补档计划| Text

POJ2391 Ombrophobic Bovines

水题,一眼就可以建立模型,二分答案+拆点最大流。然而犯了两个 SB 错误:

  • 有无解的情况,所以二分答案的时候上界不能设成和边权的 inf 一样啊……否则答案就成了 inf 了。
  • 在 floyed 之前怎么能忘记把 f[i][i] 清成 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
109
110
111
#include <bits/stdc++.h>
using namespace std;

#define N 405
#define inf 0x3f3f3f3f

int n, m, sum, a[N], b[N];
long long f[N][N];
int s, t, head[N * 2], cnt, d[N * 2];
queue<int> q;

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

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

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) 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 init()
{
    memset(head, 0, sizeof head); cnt = 1;
}

bool check(long long mid)
{
    init();
    for (int i = 1; i <= n; ++i)
        add(s, i, a[i]), add(i, s, 0),
        add(n + i, t, b[i]), add(t, n + i, 0);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (f[i][j] <= mid)
                add(i, n + j, inf), add(n + j, i, 0);
    return sum == dinic();
}

int main()
{
    memset(f, 0x3f, sizeof f);
    cin >> n >> m;
    s = 0; t = n + n + 1;
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &a[i], &b[i]), sum += a[i];
    for (int i = 1; i <= n; ++i)
        f[i][i] = 0;
    for (int x, y, z, i = 1; i <= m; ++i)
        scanf("%d%d%d", &x, &y, &z),
        f[x][y] = min(f[x][y], 1ll * z), f[y][x] = min(f[y][x], 1ll * z);
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    long long l = 0, r = 0x3f3f3f3f3f3f3f00ll, ans = -1;
    while (l <= r)
    {
        long long mid = (l + r) >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}

POJ1149 PIGS

写起来挺愉悦的。为了实现最小化边数,用了 set >o<

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

#define N 1005
#define inf 0x3f3f3f3f

int n, m, s, t, a[N], v[N], d[N];
set<int> pre;
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;
}

int head[N];

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

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

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 = m + 1;
    for (int i = 1; i <= n; ++i)
        a[i] = read(), v[i] = 0;
    for (int x, y, sum, i = 1; i <= m; ++i)
    {
        x = read(); sum = 0;
        for (int j = 1; j <= x; ++j)
        {
            y = read();
            if (!v[y]) sum += a[y];
            else pre.insert(v[y]);
            v[y] = i;
        }
        if (sum) add(s, i, sum), add(i, s, 0);
        for (set<int>::iterator j = pre.begin(); j != pre.end(); ++j)
            add(*j, i, inf), add(i, *j, 0);
        pre.clear();
        add(i, t, read()), add(t, i, 0);
    }
    cout << dinic() << endl;
    return 0;
}

POJ1637 Sightseeing tour

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

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

int test, n, m, sum, x[M], y[M], z[M], in[N], out[N];
int s, t, head[N], cnt = 1, d[N];
vector<int> v;
queue<int> q;

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

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

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 init()
{
    memset(head, 0, sizeof head); cnt = 1;
    memset(in, 0, sizeof in);
    memset(out, 0, sizeof out);
    v.resize(0); sum = 0;
}

int main()
{
    cin >> test;
    while (test--)
    {
        init();
        cin >> n >> m;
        t = n + 1;
        for (int i = 1; i <= m; ++i)
        {
            cin >> x[i] >> y[i] >> z[i];
            ++out[x[i]], ++in[y[i]];
            if (z[i] == 0) v.push_back(i);
        }
        for (int i = 1; i <= n; ++i)
        {
            if ((out[i] - in[i]) % 2) goto end;
            in[i] = (out[i] - in[i]) / 2;
            if (in[i] < 0)
                add(s, i, -in[i]), add(i, s, 0), sum += -in[i];
            else if (in[i] > 0)
                add(i, t, in[i]), add(t, i, 0);
        }
        for (int i = 0; i < (int)v.size(); ++i)
            add(y[v[i]], x[v[i]], 1), add(x[v[i]], y[v[i]], 0);
        if (sum == dinic())
            { puts("possible"); continue; }
        end : puts("impossible");
    }
    return 0;
}

POJ2699 The Maximum Number of Strong Kings

这读入可真是神了。

PDF 里面说的做法好像有点麻烦。实际上选手并不需要拆点,只需要在建图的时候保证想成为 king 的人和得分更高的人之间的比赛只与这个人连边,然后如果最大流等于比赛场数就合法。

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

#define inf 0x3f3f3f3f

int test, n, num[15], pos[15][15];
int s, t, head[200], cnt, d[200];
queue<int> q;

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[10000];

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

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

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) 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;
}

bool check(int x)
{
    init();
    for (int i = 1; i < x; ++i)
        for (int j = i + 1; j <= n; ++j)
            add(i, pos[i][j], 1), add(pos[i][j], i, 0),
            add(j, pos[i][j], 1), add(pos[i][j], j, 0);
    for (int i = x; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
        {
            add(i, pos[i][j], 1), add(pos[i][j], i, 0);
            if (num[i] == num[j])
                add(j, pos[i][j], 1), add(pos[i][j], j, 0);
        }
    for (int i = 1; i <= n; ++i)
        add(s, i, num[i]), add(i, s, 0);
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            add(pos[i][j], t, 1), add(t, pos[i][j], 0);
    return dinic() == n * (n - 1) / 2;
}

int main()
{
    test = read(); read();
    while (test--)
    {
        init();
        int x = 0; n = 1;
        while ((x = read()) == -1);
        num[1] = x;
        while ((x = read()) != -1)
            num[++n] = x;
        s = 0; t = n + n * (n - 1) / 2 + 1;
        for (int tot = n, i = 1; i <= n; ++i)
            for (int j = i + 1; j <= n; ++j)
                pos[i][j] = ++tot;
        for (int i = n; i; --i)
        {
            if (!check(i))
                { cout << n - i << endl; break; }
            if (i == 1)
                cout << n << endl;
        }
    }
    return 0;
}

POJ3281 Dining

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

#define inf 0x3f3f3f3f

int n, s1, s2;
int s, t, head[405], cnt = 1, d[405];
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, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[50000];

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

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) 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 >> s1 >> s2;
    t = s1 + s2 + n * 2 + 1;
    for (int i = 1; i <= s1; ++i)
        add(s, i, 1), add(i, s, 0);
    for (int i = 1; i <= s2; ++i)
        add(s1 + i, t, 1), add(t, s1 + i, 0);
    for (int x, y, z, i = 1; i <= n; ++i)
    {
        cin >> x >> y;
        add(s1 + s2 + i, s1 + s2 + n + i, 1),
        add(s1 + s2 + n + i, s1 + s2 + i, 0);
        for (int j = 1; j <= x; ++j)
            add(z = read(), s1 + s2 + i, 1),
            add(s1 + s2 + i, z, 0);
        for (int j = 1; j <= y; ++j)
            add(s1 + s2 + n + i, s1 + (z = read()), 1),
            add(s1 + z, s1 + s2 + n + i, 0);
    }
    cout << dinic() << endl;
    return 0;
}

ZOJ2760 How Many Shortest Path

Floyed 后向网络流图加入可能在最短路中的边,然而原题并不保证 f[i][i]=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
#include <bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f

int n, r[205][205], f[205][205];
int s, t, head[205], cnt = 1, d[205];
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, val;
    graph() {}
    graph(int _next, int _to, int _val)
    : next(_next), to(_to), val(_val) {}
} edge[100000];

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

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

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) 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()
{
    while (cin >> n)
    {
        init();
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
            {
                r[i][j] = read();
                if (i == j) r[i][j] = 0;
                f[i][j] = r[i][j] == -1 ? inf : r[i][j];
            }
        s = read() + 1; t = read() + 1;
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
        if (s == t) { puts("inf"); continue; }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (i != j && r[i][j] != -1 
                    && f[s][i] + r[i][j] + f[j][t] == f[s][t])
                    add(i, j, 1), add(j, i, 0);
        cout << dinic() << endl;
    }
    return 0;
}

WOJ1124 Football Coach

逗逼把 dfs 的函数类型定义成 bool 了……

  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 1500
#define M 100005
#define inf 0x3f3f3f3f

int n, m, score[N], sum;
int s, t, head[N], cnt, d[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[M];

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

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 init()
{
    memset(head, 0, sizeof head); cnt = 1; sum = 0;
}

int main()
{
    ios::sync_with_stdio(false);
    while (cin >> n >> m)
    {
        init();
        s = 0; t = m + n;
        for (int i = 1; i <= n; ++i)
            cin >> score[i];
        for (int x, y, i = 1; i <= m; ++i)
        {
            cin >> x >> y;
            if (x == n || y == n) score[n] += 2;
            else
            {
                sum += 2;
                add(s, i, 2), add(i, s, 0);
                add(i, m + x, 2), add(m + x, i, 0);
                add(i, m + y, 2), add(m + y, i, 0);
            }
        }
        for (int i = 1; i < n; ++i)
            if (score[i] >= score[n])
                { cout << "NO" << endl; goto end; }
        for (int i = 1; i < n; ++i)
            add(m + i, t, score[n] - score[i] - 1), add(t, m + i, 0);
        if (dinic() == sum) cout << "YES" << endl;
        else cout << "NO" << endl;
        end:;
    }
    return 0;
}

SGU438 The Glorious Karlutka River =)

在普通的流量限制上增加了时间限制。发现如果存在答案的话,答案不会大于 n+m(一个接一个走一条长度为 n 的路线)。因此枚举答案,将每一个点在时间的维度上再拆成很多点。大概模型就是“从 t 时刻的垃圾 i 可以跳到 t+1 时刻的垃圾 j 上”。

  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 inf 0x3f3f3f3f

int n, m, dis, w, x[55], y[55], c[55], dist[55][55];
int s, t, head[20000], cnt = 1, d[20000];
queue<int> q;

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

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

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;
}

inline int pos(int x, int y, int z)
{
    return (n * y + x) * 2 + z;
}

int main()
{
    cin >> n >> m >> dis >> w;
    s = 0; t = 1;
    if (dis >= w) { puts("1"); return 0; }
    for (int i = 1; i <= n; ++i)
        cin >> x[i] >> y[i] >> c[i];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            dist[i][j] = (x[i] - x[j]) * (x[i] - x[j]) +
                         (y[i] - y[j]) * (y[i] - y[j]) - dis * dis;
    for (int cnt = 0, ans = 1; ans > 0; ++ans)
    {
        if (ans > n && cnt == 0)
            { puts("IMPOSSIBLE"); return 0; }
        for (int i = 1; i <= n; ++i)
        {
            add(pos(i, ans, 0), pos(i, ans, 1), c[i]),
            add(pos(i, ans, 1), pos(i, ans, 0), 0);
            for (int j = 1; j <= n; ++j)
                if (dist[j][i] <= 0)
                    add(pos(j, ans - 1, 1), pos(i, ans, 0), inf),
                    add(pos(i, ans, 0), pos(j, ans - 1, 1), 0);
            if (y[i] <= dis)
                add(s, pos(i, ans, 0), inf), add(pos(i, ans, 0), s, 0);
            if (w - y[i] <= dis)
                add(pos(i, ans, 1), t, inf), add(t, pos(i, ans, 1), 0);
        }
        cnt += dinic();
        if (cnt >= m)
            { cout << ans + 1 << endl; return 0; }
    }
    return 0;
}

SPOJNETADMIN Smart Network Administrator

一眼二分答案。在解题过程中完全不需要在意双向边什么的,因为如果在一条边上有两条方向不同的线经过,还不如它们各自都不经过这条边。

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

#define N 550
#define M 250000
#define inf 0x3f3f3f3f

int test, n, m, k, h[N], x[M], y[M];
int s, t, head[N], cnt = 1, d[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[250000];

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

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 init()
{
    memset(head, 0, sizeof head); cnt = 1;
}

bool check(int mid)
{
    init();
    for (int i = 1; i <= k; ++i)
        add(h[i], t, 1), add(t, h[i], 0);
    for (int i = 1; i <= m; ++i)
        add(x[i], y[i], mid), add(y[i], x[i], mid);
    return dinic() == k;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> test;
    while (test--)
    {
        cin >> n >> m >> k;
        s = 1; t = n + 1;
        for (int i = 1; i <= k; ++i)
            cin >> h[i];
        for (int i = 1; i <= m; ++i)
            cin >> x[i] >> y[i];
        int l = 1, r = k, ans = 0;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (check(mid)) ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout << ans << endl;
    }
    return 0;
}

SPOJIM Intergalactic Map

不能用 cin 读入!

换一种思考方式,将是否可以从 1 走到 2 再走到 3 转化为 2 同时走到 1 和 3。这样就可以将源点设在 2 的出点,1 和 3 的出点分别向汇点连边。判断最大流是否是 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
#include <bits/stdc++.h>
using namespace std;

#define N 65000
#define M 300005
#define inf 0x3f3f3f3f

int test, n, m;
int s, t, head[N], cnt = 1, d[N];
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, 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;
}

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 init()
{
    memset(head, 0, sizeof head); cnt = 1;
}

inline int pos(int x, int y)
{
    return x * 2 + y;
}

int main()
{
    cin >> test;
    while (test--)
    {
        init();
        n = read(); m = read();
        for (int i = 1; i <= n; ++i)
            add(pos(i, 0), pos(i, 1), 1), add(pos(i, 1), pos(i, 0), 0);
        for (int x, y, i = 1; i <= m; ++i)
        {
            x = read(); y = read();
            if (x > n || y > n) continue;
            add(pos(x, 1), pos(y, 0), 1), add(pos(y, 0), pos(x, 1), 0),
            add(pos(y, 1), pos(x, 0), 1), add(pos(x, 0), pos(y, 1), 0);
        }
        s = pos(2, 1); t = 1;
        add(pos(1, 1), t, 1), add(t, pos(1, 1), 0);
        add(pos(3, 1), t, 1), add(t, pos(3, 1), 0);
        if (dinic() == 2) puts("YES");
        else puts("NO");
    }
    return 0;
}