一个奇怪的想法,关于欧拉回路
查看原帖
一个奇怪的想法,关于欧拉回路
648705
Glax712124楼主2024/11/25 11:37

众所周知,P2731 [USACO3.3] 骑马修栅栏 Riding the Fences是欧拉回路的板子题。

这是题解区第一篇@EarthGiao大佬的题解代码:

//防伪标识
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int map[10001][10001];//记录两个点之间的路径个数 
int du[10001];//辅助记录奇点 
int lu[10001];//记录路径 
int n,x,y,js=0;
int maxn=0;
void find(int i)//
{
	int j;
	for(j=1;j<=maxn;++j)//而且这里不是n而是maxn因为n不是点的个数而是下面有多少行 
	{
		if(map[i][j]>=1)
		{
			map[i][j]--;//删去边一次吗避免重复 
			map[j][i]--;//z这里和一笔画不一样这里是累减而一笔画直接变成0 
			find(j);
                       (******①******)
		}
	}
	lu[++js]=i;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&x,&y);
		map[x][y]++;
		map[y][x]++;
		du[x]++;
		du[y]++;//记录出现的次数 
		maxn=max(maxn,max(x,y));
	}
	int start=1;//默认奇点是1 
	for(int i=1;i<=maxn;++i)
	{
		if(du[i]%2)//找到奇点 
		{
			start=i;//记录奇点
			break;//然后结束循环 
		}
	}
	find(start);//从奇点开始找 
	for(int i=js;i>=1;i--)
	{
		printf("%d\n",lu[i]);//挨个输出路径并且换行 
	}
	return 0;
}

为什么在①这个地方加个break就错了呢?

理论上没有问题啊!

求反例,谢谢大佬。

2024/11/25 11:37
加载中...