定義

歐拉路：從圖中一個點s出發(fā)，到圖中的一點t，經(jīng)過每條邊且每條邊僅經(jīng)過一次
歐拉回路：歐拉路中s==t

判定條件

• 無向圖 所有邊聯(lián)通

1. 存在歐拉路：度數(shù)為奇數(shù)的點的個數(shù)為0或2
2. 存在歐拉回路：度數(shù)為奇數(shù)的點的個數(shù)為0

• 有向圖 所有邊聯(lián)通

1. 存在歐拉路：
   所有點的入度==出度
   或
   除起點（出度==入度+1）和終點（入度==出度+1）外，其他點的入度==出度
2. 存在歐拉回路：除起點（出度==入度+1）和終點（入度==出度+1）外，其他點 的入度==出度

可以看出歐拉回路是歐拉路的一種特殊情況

例題

• 鏟雪車
  思路:
  1. 保證：鏟雪車從起點一定可以到達任何街道。說明鏟雪車在某條街道上
  2. 可以判定每個點的入度==出度，時間最短所對應(yīng)的路徑為歐拉回路的路徑，則時間=路徑/速度即可

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int main(){
    double x1,y1,x2,y2,sum=0;
    cin>>x1>>x2;
    while(cin>>x1>>y1>>x2>>y2){
        double x=x2-x1,y=y2-y1;
        sum+=sqrt(x*x+y*y)*2;
    }
    int minutes=round(sum/1000/20*60);//四舍五入函數(shù) cmath中 
    int hours=minutes/60;
    minutes%=60;
    printf("%d:%02d",hours,minutes);//%02d 為保留整數(shù)最低的兩位 不足用前導(dǎo)零補齊 
    
    return 0;
}