欧拉回路 T2 随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。整个城市所有的道路都是双车道，因为城市预算的削减，整个城市只有1辆铲雪车。铲雪车只能把它开过的地方（车道）的雪铲干净，无论哪儿有雪，铲雪车都得从停放的地方出发，游历整个城市的街道。现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？
输入
输入数据的第1行表示铲雪车的停放坐标（x,y），x，y为整数，单位为米。下面最多有100行，每行给出了一条街道的起点坐标和终点坐标，所有街道都是笔直的，且都是双向一个车道。铲雪车可以在任意交叉口、或任何街道的末尾任意转向，包括转U型弯。铲雪车铲雪时前进速度为20 km/h，不铲雪时前进速度为50 km/h。 保证：铲雪车从起点一定可以到达任何街道。
输出
铲掉所有街道上的雪并且返回出发点的最短时间，精确到分种。
输入样例
0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000输出样例
3:55思路
给一个无向图, 其中每个点都可以达到其他任意一个点, 全连通图。 让我们求一条耗时最短的路径, 经过所有的边, 并且回到起点, 也就是欧拉回路问题。
-
对于无向图，所有边都是连通的。 (1)存在欧拉路径的充分必要条件:度数为奇数的点只能有0或2个。 (2)存在欧拉回路的充分必要条件:度数为奇数的点只能有0个。
-
对于有向图，所有边都是连通。 (1)存在欧拉路径的充分必要条件:要么所有点的出度均等于入度;要么除了两个点之外，其余所有点的出度等于入度，剩余的两个点:一个满足出度比入度多1(起点)，另一个满足入度比出度多1(终点). (2)存在欧拉回路的充分必要条件:所有点的出度均等于入度。
可以发现, 该图一定是存在欧拉回路, 那么总时间数就是所有边的耗时和的二倍, 因为双向道路都需要铲雪, 看做有向图即可。
最后再做一个时间转换。
代码
#define S second
#define F first
#define pb push_back
#define pf push_front
#define lson l, mid, u << 1
#define rson mid + 1, r, u << 1 | 1
#define MID l + r >> 1
#define mem(x, n) memset(x, n, sizeof x)
#define setPrec(n) cout << fixed << setpricision(n)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
using i64 = long long;
// #define debug
void solve()
{
double x1, x2, y1, y2;
cin >> x1 >> x2;
double sum = 0;
while (cin >> x1 >> y1 >> x2 >> y2)
{
double dx = x2 - x1;
double dy = y1 - y2;
sum += sqrt(dx * dx + dy * dy) * 2;
}
int time = round(sum / 1000 / 20 * 60);
// cout << time << endl;
printf("%d:%02d\n", time / 60, time % 60);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
getchar();
getchar();
while (T--)
{
solve();
if (T)
{
getchar();
puts("");
}
}
return 0;
}