题目解答

来源：acwing

分析：

对于一个给定的图，怎样判断是否存在着一个恰好包含了所有的边，并且没有重复的路径？这就是一笔画问题。用图论的术语来说，就是判断这个图是否是一个能够遍历完所有的边而没有重复。这样的图现称为欧拉图。这时遍历的路径称作欧拉路径（一个环或者一条链），如果路径闭合（一个圈），则称为欧拉回路。

一笔画定理：

无向图的一笔画

连通的无向图 $G$有欧拉路径的充要条件是：$G$中奇顶点（连接的边数量为奇数的顶点）的数目等于0或者2。

连通的无向图 $G$ 是欧拉环（存在欧拉回路）的充要条件是：$G$中每个顶点的度都是偶数。

有向图的一笔画

一个连通有向图$G$有欧拉路径，指存在一个顶点，从它出发，沿着有向边的方向，可以不重复地遍历图中所有的边。

有向图的欧拉回路则是指可以从某一顶点开始，沿有向边的方向不重复地遍历所有边，然后回到原来出发的顶点。

一个连通的有向图可以表示为一条从顶点$u$到$v$的（不闭合的）欧拉路径的充要条件是：

• $u$的出度（从这个顶点发出的有向边的数量）比入度（指向这个顶点的有向边的数量）多1，$v$的出度比入度少1，
• 而其它顶点的出度和入度都相等。

一个连通的有向图是欧拉环（存在欧拉回路）的充要条件是以下两个之一：

• 每个顶点的出度和入度都相等；
• 存在一系列的（有向）环$C_1,C_2,\cdots ,C_m$，使得图$G$里的每一条边都恰好属于某一个环。

来源：维基百科

对于本题：

因为题目告诉了铲雪车从起点一定可以到达任何街道，并且本题所有边都是双向的，而且每个点的出度和入度都相等。所以一定是欧拉回路，可以一笔画，这样的话就是求每条道路的长度。

看似是欧拉路径求长度的问题，实际上是一道脑筋急转弯问题，只需要求出每条路的长度，由于是双向的，所以需要乘以2，然后除以铲雪的速度,就可以求出总的时间，然后进行四舍五入求分钟。

ac代码

#include<bits/stdc++.h>
using namespace std;
const int N = 4010;
// 本题的图中所有点的入度和出度都是相等的,所以存在欧拉回路
typedef long long LL;

double get(double x1, double y1, double x2, double y2){
    double dx = x1 - x2;
    double dy = y1 - y2;
    return sqrt(dx * dx + dy * dy) * 2; 
}
int main(){
    double x,y;
    cin >> x >> y;
    double sum = 0;
    double x1, y1, x2, y2;
    while(cin >>x1 >> y1 >> x2 >> y2){
        sum += get(x1, y1, x2, y2);
    }
    
    int minutes = round(sum/ 1000 /20 * 60);
    int hours = minutes / 60;
    minutes  %= 60;
    printf("%d:%02d", hours, minutes);
}

题目来源

https://www.acwing.com/problem/content/1125/