USACO备考冲刺必刷题 | P2913 Wheel Rotation

学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考学习过程中的题目，记录每一个瞬间。

附上汇总贴：USACO备考冲刺必刷题 | 汇总-CSDN博客

---

【题目描述】

约翰有一个过时的收割机，需要在它的各种滑轮上装配皮带才能让收割机的各个部分运作起 来.引擎能够驱动滑轮1向顺时针方向转动，滑轮1通过一条皮带又连接到滑轮2.滑轮2又通过一 条皮带连接到滑轮3，等等，总共有N(2 <= N <= 1000)个滑轮和N - 1条皮带.

皮带连接两个滑轮有两种方式：直接连接和交叉连接.直接连接的两个滑轮旋转方向相同， 即同为顺时针或同为逆时针.交叉连接的两个滑轮旋转方向相反.

现在给出一个列表，里面列出所有皮带的连接方式.已经知道滑轮1被引擎驱动着向顺时针方 向转动.每一条皮带由下面三个数定义：

?驱动滑轮S，输入驱动力的滑轮.

?被驱动滑轮D;，被驱使转动的滑轮.

?连接类型C，0表示直接连接，1表示交叉连接.

不幸的是，约翰的这个列表中，皮带的顺序是混乱的.所以请你写一个程序来求出滑轮N的 转动方向.

【输入】

• Line 1: A single integer: N
• Lines 2..N: Each line describes a belt with three integers: S_i, D_i, and C_i

【输出】

• Line 1: A single integer that is the rotation direction for pulley N (0=clockwise, 1=counterclockwise)

【输入样例】

4 
2 3 0 
3 4 1 
1 2 0

【输出样例】

1

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n;
struct node {
    int s, d, c;
}p[1005];
bool cmp(node a, node b) {
    return a.s < b.s;
}
int a[1005];
int main()
{
    a[1] = 0;  // 第1个轮的方向为顺时针
    cin >> n;  // 输入n
    for (int i=1; i<n; i++) {  // 遍历n-1对数据
        cin >> p[i].s >> p[i].d >> p[i].c;  // 记录每2个齿轮的S、D和C
    }
    sort(p+1, p+n, cmp);  // 按照齿轮编号从小到大排序
    for (int i=1; i<=n; i++) {  // 遍历n-1对数据
        if (p[i].c==0) {  // 如果直接连接
            a[p[i].d] = a[p[i].s];  // D轮的方向与S轮的方向相同
        } else {  // 如果是交叉连接
            a[p[i].d] = !(a[p[i].s]);  // D轮的方向与S轮方向相反
        }
    }
    cout << a[n];  // 输出最后一个轮的方向
    return 0;
}

【运行结果】

4 
2 3 0
3 4 1
1 2 0
1