P2731 [USACO3.3] 骑马修栅栏 Riding the Fences

本题重点考察欧拉回路的了解和图论的扎实，如果不了解欧拉回路的朋友们点以下按钮前往爱因斯浩大佬的浩浩妙妙屋学习：（图论基础自己学）

ION大佬

$\color{black} \def\arraystretch{1.25} \begin{array}{|c|} \hline \color{read}\texttt{爱因斯浩的浩浩妙妙屋} \\ \hline \end{array}$

根据题意，我们有m条边和小于500个顶点，第一步就是输入并存储我们的图，并且可以用邻接表表示边的关系（只有500）还要求最大顶点编号 ：

for(int i=1;i<=n;i++){
   cin>>x>>y;
	V[x].push_back(y); 
	V[y].push_back(x);//无向图 
	m=max(m,max(x,y));//求最大顶点编号 
	r[x][y]++;
	r[y][x]++;//无向图 
}

由于输出要按题目所要求的排列，所以我们要再对每一个顶点所可以到达的点进行排序（从小到大排序），也就是我们的vector[i]（1~m）:

for(int i=1;i<=m;i++){
    sort(V[i].begin(),V[i].end());//vector的排序  
}

然后，我们根据欧拉回路的性质，开始寻找我们的第一个奇数点（简称奇点）

for(int i=1; i<=m; i++)
	if(V[i].size()%2) { //奇点
		pd(i);
		f=1;
		break;
}

注释：这里的f表示是否找到有奇点，如果不存在奇数点，寻找第一个有效点 ：

if(!f) { //没找到奇点
	for(int i=1; i<=m; i++) {
		if(V[i].size()) {
			pd(i);
			break;
		}
	}
}

而接下来，就到了本题的关键，也就是上述代码中的PD（判断，我也不知道为什么我会取这样一个名字（可能习惯了）），他是欧拉回路的核心，也就是我们常说的搜索：

void pd(int p) {
	for(int i=0; i<V[p].size(); i++)
		if(r[p][V[p][i]]) {
			r[p][V[p][i]]--;
			r[V[p][i]][p]--;
			pd(V[p][i]);
		}
	ans[++l]=p;
}

接下来我来解释一下代码

for(int i=0; i<V[p].size(); i++)
	if(r[p][V[p][i]])

不用多说，枚举点可以到的所有点,判断是两点间否有边

r[p][V[p][i]]--;
r[V[p][i]][p]--;

把我们已经寻找过两点间的无向边删去（等于标记已经找过了）

pd(V[p][i]);

搜索下一个点

ans[++l]=p;

把我们的答案存进ans数组里（因为不知道具体的答案长度，所以用ans[++l]写）

最后到了收尾阶段

for(int i=1; i<=l; i++)
      cout<<ans[i]<<"\n";

错了，我们的答案应该是反向搜索所存，所以应该反向输出

for(int i=l; i>=1; i--)
		cout<<ans[i]<<"\n";

最后

return 0;

华丽的结束！

最后附上AC代码：

#include <bits/stdc++.h>
using namespace std;
vector<int> V[501];
int n,m,x,y;
int r[501][501],ans[1080];
int f,l;
void pd(int p) {
	for(int i=0; i<V[p].size(); i++)
		if(r[p][V[p][i]]) {
			r[p][V[p][i]]--;
			r[V[p][i]][p]--;
			pd(V[p][i]);
		}
	ans[++l]=p;
}
int main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>x>>y;
		V[x].push_back(y);
		V[y].push_back(x);//无向图
		m=max(m,max(x,y));//求最大顶点编号
		r[x][y]++;
		r[y][x]++;//无向图
	}
	for(int i=1; i<=m; i++) {
		sort(V[i].begin(),V[i].end());
	}
	for(int i=1; i<=m; i++)
		if(V[i].size()%2) { //奇点
			pd(i);
			f=1;
			break;
	}
	if(!f) { //偶点
		for(int i=1; i<=m; i++) {
			if(V[i].size()) {
				pd(i);
				break;
			}
		}
	}
	for(int i=l; i>=1; i--)cout<<ans[i]<<"\n";
	return 0;
}

觉得好给个免费的赞和掌声再走吧！

记得关注爱因斯浩大佬哦> ~ <

版权所有，未允许禁止转载！