定义
欧拉路：从图中一个点s出发，到图中的一点t，经过每条边且每条边仅经过一次
欧拉回路：欧拉路中s==t
判定条件
- 无向图 所有边联通
- 存在欧拉路：度数为奇数的点的个数为0或2
- 存在欧拉回路：度数为奇数的点的个数为0
- 有向图 所有边联通
- 存在欧拉路：
所有点的入度==出度
或
除起点（出度==入度+1）和终点（入度==出度+1）外，其他点的入度==出度 - 存在欧拉回路：除起点（出度==入度+1）和终点（入度==出度+1）外，其他点 的入度==出度
可以看出欧拉回路是欧拉路的一种特殊情况
例题
-
铲雪车
思路:- 保证：铲雪车从起点一定可以到达任何街道。说明铲雪车在某条街道上
- 可以判定每个点的入度==出度，时间最短所对应的路径为欧拉回路的路径，则时间=路径/速度即可
#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);//四舍五入函数 cmath中
int hours=minutes/60;
minutes%=60;
printf("%d:%02d",hours,minutes);//%02d 为保留整数最低的两位 不足用前导零补齐
return 0;
}
