[USACO08MAR] The Loathesome Hay Baler S

题意

给出 n 个滚轮的位置和半径。

坐标为 (0,0) 的滚轮是驱动轮；
坐标为 (Xt,Yt) 的滚轮是目标滚轮；
两个滚轮如果外切，就可以传递动力。

已知驱动轮每小时顺时针转 10000 圈。若半径为 Rd 的滚轮以速度 S 驱动半径为 Rx 的滚轮，那么后者速度变成：

-S * Rd / Rx

负号表示转向相反。

题目要我们只看“从驱动轮到目标滚轮”这一条动力链，把这条链上所有滚轮速度的绝对值加起来，最后输出截断后的整数部分。

思路

最直接的想法，是把所有相切关系建成图，然后从驱动轮一路搜到目标滚轮。搜索时顺手把当前滚轮的转速也传下去，走到目标时就能得到这条路径上的答案。

这个版本最适合理解题意：

cpp

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

const int MAXN = 1055;

int n;
int target_x, target_y;
int x[MAXN], y[MAXN], r[MAXN];
vector<int> g[MAXN];
int root_id, target_id;
bool vis[MAXN];
bool found_answer;
long double answer_sum;

bool touch(int i, int j) {
    long long dx = 1LL * x[i] - x[j];
    long long dy = 1LL * y[i] - y[j];
    long long sum_r = 1LL * r[i] + r[j];
    return dx * dx + dy * dy == sum_r * sum_r;
}

void build_graph() {
    for (int i = 1; i <= n; i++) {
        g[i].clear();
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (touch(i, j)) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
}

void find_special_nodes() {
    root_id = 0;
    target_id = 0;
    for (int i = 1; i <= n; i++) {
        if (x[i] == 0 && y[i] == 0) {
            root_id = i;
        }
        if (x[i] == target_x && y[i] == target_y) {
            target_id = i;
        }
    }
}

// 朴素做法：在相切图里直接搜从驱动轮到目标轮的那条路径，
// 搜索过程中把当前滚轮速度和前面路径上的速度和一起传下去。
void dfs(int u, long double speed_now, long double sum_now) {
    if (found_answer) {
        return;
    }

    vis[u] = true;
    sum_now += fabsl(speed_now);

    if (u == target_id) {
        answer_sum = sum_now;
        found_answer = true;
        vis[u] = false;
        return;
    }

    for (int i = 0; i < (int) g[u].size(); i++) {
        int v = g[u][i];
        if (vis[v]) {
            continue;
        }
        long double next_speed = -speed_now * (long double) r[u] / r[v];
        dfs(v, next_speed, sum_now);
    }

    vis[u] = false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> target_x >> target_y;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i] >> r[i];
    }

    build_graph();
    find_special_nodes();

    found_answer = false;
    answer_sum = 0.0L;
    memset(vis, 0, sizeof(vis));
    dfs(root_id, 10000.0L, 0.0L);

    cout << (long long) floorl(answer_sum + 1e-12L) << '\n';
    return 0;
}

如何判断两个滚轮相连

如果两个滚轮外切，那么圆心距离恰好等于半径和。

所以对于滚轮 i 和 j，只要判断：

(xi-xj)^2 + (yi-yj)^2 == (ri+rj)^2

就知道它们之间有没有边。

为什么路径是唯一的

题目保证：

除驱动轮外，每个滚轮都由某个别的滚轮驱动；
一个滚轮不会同时被两个滚轮驱动。

这意味着对于目标滚轮来说，从驱动轮走到它的动力传递链只有一条，所以我们找到目标后，沿着父节点回溯即可。

转速怎么传

若当前滚轮速度是 S，半径是 r[u]，相邻滚轮半径是 r[v]，那么：

speed[v] = -speed[u] * r[u] / r[v]

因此在 BFS / DFS 过程中，把父节点和转速一起记录下来即可。

最后从目标滚轮一直回溯到驱动轮，把这些滚轮的 |speed| 累加，就是答案。

代码

cpp

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

const int MAXN = 1055;

int n;
int target_x, target_y;
int x[MAXN], y[MAXN], r[MAXN];
vector<int> g[MAXN];
int root_id, target_id;
int parent_node[MAXN];
long double speed[MAXN];

bool touch(int i, int j) {
    long long dx = 1LL * x[i] - x[j];
    long long dy = 1LL * y[i] - y[j];
    long long sum_r = 1LL * r[i] + r[j];
    return dx * dx + dy * dy == sum_r * sum_r;
}

void build_graph() {
    for (int i = 1; i <= n; i++) {
        g[i].clear();
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (touch(i, j)) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
        }
    }
}

void find_special_nodes() {
    root_id = 0;
    target_id = 0;
    for (int i = 1; i <= n; i++) {
        if (x[i] == 0 && y[i] == 0) {
            root_id = i;
        }
        if (x[i] == target_x && y[i] == target_y) {
            target_id = i;
        }
    }
}

void bfs() {
    memset(parent_node, -1, sizeof(parent_node));

    queue<int> q;
    parent_node[root_id] = 0;
    speed[root_id] = 10000.0L;
    q.push(root_id);

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

        if (u == target_id) {
            return;
        }

        for (int i = 0; i < (int) g[u].size(); i++) {
            int v = g[u][i];
            if (parent_node[v] != -1) {
                continue;
            }
            parent_node[v] = u;
            // 两个相切滚轮的线速度相同，所以角速度与半径成反比，方向相反。
            speed[v] = -speed[u] * (long double) r[u] / r[v];
            q.push(v);
        }
    }
}

long long calc_answer() {
    long double sum = 0.0L;
    int cur = target_id;
    while (cur != 0) {
        sum += fabsl(speed[cur]);
        if (cur == root_id) {
            break;
        }
        cur = parent_node[cur];
    }
    return (long long) floorl(sum + 1e-12L);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> target_x >> target_y;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i] >> r[i];
    }

    build_graph();
    find_special_nodes();
    bfs();

    cout << calc_answer() << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n^2)$
空间复杂度： $O(n^2)$

其中 $O(n^2)$ 的时间来自枚举每一对滚轮判断是否相切；图的边数本身也是 $O(n^2)$ 级别上界。

总结

这题本质上不是物理题，而是一个“几何建图 + 图上找路径”的题。

先用“圆心距离等于半径和”把相切关系建出来，再沿着从驱动轮到目标滚轮的那条链递推转速，问题就做完了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。