铲雪车骑马修栅栏（欧拉路径和欧拉回路）

今天上午的训练赛涉及到的，顺便补一下叭。

一.定义

相信大家都听说过著名的七桥问题，而欧拉回路就是伟大的数学家欧拉为了解决七桥问题提出的。
首先介绍一下基本概念：在一个图中，经过每条边一次并且只经过一次的回路被称为欧拉回路，路径被称为欧拉路径。根据名字就可以知道，回路是起点终点相同的，而路径是起点终点不同的。
其实欧拉路径就是小时候玩的一笔画游戏（真是万物皆可图论）

二：性质和定理

特性：起点和终点的度都是奇数，中间点的度数必是偶数

结论：

1.在无向图中，所有边都连通：

（1）存在欧拉路径的充要条件：所有点度数为奇数的点只能有0或2个

（2）存在欧拉回路（起点和终点重合）的充要条件：度数为奇数的点只能有0个

2.在有向图中，所有边都连通：

（1）存在欧拉路径的充要条件：要么所有点的出度均等于入度；要么除了两个点之外，其余所有点的出度等于入度，剩余两个点：一个出度比入度多1，另一个入度比出度多1.

（2）存在欧拉回路（起点和终点重合）的充要条件：所有点的出度均等于入度。

结论很好证明的，在此不多做叙述。

三.题目

铲雪车

题目描述
随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。整个城市所有的道路都是双车道，因为城市预算的削减，整个城市只有1辆铲雪车。铲雪车只能把它开过的地方（车道）的雪铲干净，无论哪儿有雪，铲雪车都得从停放的地方出发，游历整个城市的街道。现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？
输入
输入数据的第1行表示铲雪车的停放坐标（x,y），x，y为整数，单位为米。下面最多有100行，每行给出了一条街道的起点坐标和终点坐标，所有街道都是笔直的，且都是双向一个车道。铲雪车可以在任意交叉口、或任何街道的末尾任意转向，包括转U型弯。铲雪车铲雪时前进速度为20 km/h，不铲雪时前进速度为50 km/h。
保证：铲雪车从起点一定可以到达任何街道。
输出
铲掉所有街道上的雪并且返回出发点的最短时间，精确到分种。
样例输入 Copy
0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000
样例输出 Copy
3:55
提示
3小时55分钟
题意： 给你一个无向图，问经过所有路径并回到起点的最短路。
思路： 这个题只是用到了欧拉回路的思想，具体代码的话直接算就可以。先来理解一下怎么样才能使得路径最短。因为题目中说可以在任意位置任意转向，要想时间最短，只需要将每条路都走一遍再回到起点即可。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
double dis(double x1,double y1,double x2,double y2){
    return (double)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));//欧几里德距离
}
void AC(){
    double x,y,x1,x2,y1,y2;
    cin>>x>>y;
    double sum=0;
    while(cin>>x1>>y1>>x2>>y2)
        sum+=dis(x1,y1,x2,y2);
    sum=sum*2/1000/20;//因为每条道路都是双车道，所以要*2，剩下的就是时间的转换了
    int h=sum;
    sum*=60;
    int min=sum-h*60+1;//要向上取整 
    printf("%d:%02d",h,min);//保持输出格式
}
int main(){
    AC();
    return 0;
}

骑马修栅栏

题目描述
农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。

John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。

每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。

你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。输入数据保证至少有一个解。
输入
第1行: 一个整数F(1 <= F <= 1024)，表示栅栏的数目
第2到F+1行: 每行两个整数i, j(1 <= i,j <= 500)表示这条栅栏连接i与j号顶点。
输出
输出应当有F+1行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。
样例输入 Copy
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6
样例输出 Copy
1
2
3
4
2
5
4
6
5
7

题意： 给你一个无向图，要求从任意一点出发，经过所有边，在某一点结束，输出字典序最小的路径。
思路： 这个题要注意的就是dfs过程中枚举出点的顺序。因为题目中要求字典序最小，第一反应可能是枚举的时候从大到小枚举，这样倒序输出路径还原时就是字典序最小了。但是！真的是这样吗？答案是否定的。可以看一下前面欧拉回路的定义，这就要求了从一个点出去遍历几个点之后再回到这个点，我们来举个例子：比如1，3，5.如果我们先枚举1的话，就意味着从1出去的一条路会把3和5串联起来，这也就保证了1是最后加到答案中的，逆序输出后，就在前面。所以枚举时就从小到大枚举就好了！

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1100;
int n=500,m;
int g[maxn][maxn];
int ans[maxn],cnt;
int tot[maxn];
void dfs(int u){
	//1 3 5 起点最后被加进去 
	for(int i=1;i<=n;i++)
		if(g[u][i]){
			g[u][i]--;g[i][u]--;
			dfs(i);
		}
	ans[++cnt]=u;
}
int main(){
	cin>>m;
	while(m--){
		int a,b;
		cin>>a>>b;
		g[a][b]++;g[b][a]++;
		tot[a]++,tot[b]++;
	}
	int s=1;
	while(!tot[s]) s++;
	for(int i=1;i<=n;i++)
		if(tot[i]%2){
			s=i;
			break;
		}
	dfs(s);
	for(int i=cnt;i;i--) cout<<ans[i]<<endl;
	return 0;
}

万物皆可图论

不当之处，请多指教~