題目： UVa - 12125 - March of the Penguins

題目說明

給定一些冰塊，每個冰塊上有一些企鵝，每個冰塊有一個可以跳出的次數限制，每個冰塊位於一個坐標，現在每個企鵝跳躍力為d，問所有企鵝能否跳到一點上，如果可以輸出所有落腳冰塊，如果沒有方案就打印 -1。

UVA 12125 - March of the Penguins（最大流）_Remilia’s-CSDN博客

解題思路

最大流，依照上面的說明建邊後使用 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
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
152
153
154
155
156
157
158
159
160
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define CLR(c) memset(c, 0, sizeof(c))

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

template <typename T>
T QPOP(queue<T>& q)
{
    T tmp = q.front();
    q.pop();
    return tmp;
}

struct Point
{
    int x;
    int y;
    int n;
    int m;

    void read() { cin >> x >> y >> n >> m; }
};

// reference: https://ppt.cc/fHi3ax

const int INF = (int)1e9;
const int MXN = 205;

int S, T;
int rn[MXN][MXN];
int l[MXN];

int N;
double D;
int tot;
Point p[MXN];

double dist(const Point& l, const Point& r)
{
    return sqrt(pow(l.x - r.x, 2) + pow(l.y - r.y, 2));
}

void read()
{
    cin >> N >> D;

    tot = 0;
    T = N * 2 + 1;
    FOR(i, 1, N + 1) p[i].read(), tot += p[i].n;
}

void build(int u)
{
    CLR(rn);

    FOR(i, 1, N + 1)
    {
        rn[S][i] = p[i].n;

        // 冰塊的跳出限制
        if (i == u) rn[u][u + N] = INF;
        else rn[i][i + N] = p[i].m;

        FOR(j, i + 1, N + 1)
        {
            if (dist(p[i], p[j]) > D) continue;
            rn[i + N][j] = INF;
            rn[j + N][i] = INF;
        }
    }

    rn[u + N][T] = INF;
}

bool dinicBFS()
{
    CLR(l);

    queue<int> q;
    q.push(S);
    l[S] = 1;

    while (!q.empty())
    {
        int u = QPOP(q);

        FOR(v, 0, T + 1)
        {
            if (l[v] || !rn[u][v]) continue;
            l[v] = l[u] + 1;
            q.push(v);
        }
    }

    return l[T];
}

int dinicDFS(int u, int cp)
{
    if (u == T) return cp;

    int tmp = cp;

    FOR(v, 0, T + 1 && tmp)
    {
        if (l[v] != l[u] + 1 || !rn[u][v]) continue;
        int bt = dinicDFS(v, min(rn[u][v], tmp));
        rn[u][v] -= bt;
        rn[v][u] += bt;
        tmp -= bt;
    }

    return cp - tmp;
}

int maximumFlow()
{
    int mf = 0;
    while (dinicBFS()) mf += dinicDFS(S, INF);
    return mf;
}

void solve()
{
    int cnt = 0;

    FOR(i, 1, N + 1)
    {
        build(i);
        if (maximumFlow() == tot)
        {
            if (cnt++) cout << ' ';
            cout << i - 1;
        }
    }

    if (!cnt) cout << "-1\n";
    else cout << '\n';
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        read();
        solve();
    }
}

參考資料

UVA 12125 - March of the Penguins（最大流）_Remilia’s-CSDN博客