AcWing 1123. 铲雪车

题目传送门

一、前导知识

1、对于无向图，所有边都是连通的。

• 存在欧拉路径的充分必要条件：度数为奇数的点只能有\(0\)或\(2\)个。
• 存在欧拉回路的充分必要条件：度数为奇数的点只能有\(0\)个。

2、对于有向图，所有边都是连通。

• 存在欧拉路径的充分必要条件：要么所有点的出度均等于入度；要么除了两个点之外，其余所有点的出度等于入度，剩余的两个点：一个满足出度比入度多\(1\)（起点），另一个满足入度比出度多\(1\)（终点）
• 存在欧拉回路的充分必要条件：所有点的出度均等于入度。

3、欧拉回路：可以从任意点开始搜索
欧拉路径：从度数的奇数点开始搜索

二、题目解析

我们将这个图看成有向图，对于每输入一组数据加两条有向边，需要每条边都至少走一遍

因此，我们考虑每加一条边，每个点的入度和出度都加\(1\),所以，每个点的入度都一定等于出度,符合上述的\(2(2)\)

故这个图存在欧拉回路,可以从任意点出发，只需统计所有的边的长度总和，跟据\(20km/h\) 算出时间即可

注意一下
\(50km/h\)的速度在本题中没有任何作用
图不需要建出

三、实现代码

#include 

using namespace std;

int main() {
    double x1, y1, x2, y2;
    cin >> x1 >> y1;
   
    double sum = 0;
    while (cin >> x1 >> y1 >> x2 >> y2) {
        double dx = x1 - x2;
        double dy = y1 - y2;
        //欧几里得距离
        // sum += sqrt(dx * dx + dy * dy) * 2;
        sum += hypot(dx, dy) * 2;
    }
    // 20千米/小时
    int minutes = round(sum / 1000 / 20 * 60);
    int hours = minutes / 60;
    minutes %= 60;
    printf("%d:%02d\n", hours, minutes);
    return 0;
}