首页 > 代码库 > 骑马修栅栏--一种较为慢的做法

骑马修栅栏--一种较为慢的做法

一种挺简单的做法,欧拉标准算法,贴上程序

vvvvvv

#include<iostream>
#include<cstring>
#include<string>
#include<fstream>
#include<queue>
#include<climits>
#include<vector>
using namespace std;
int Max(int a,int b) { return a>b?a:b; }
int Min(int a,int b) { return a<b?a:b; }
int map[505][505];
int path[1050];
int pathnum;
int minv=INT_MAX,maxv=0;
void Euler_circle_u(int v)
{
for (int i=minv;i<=maxv;i++)
while(map[i][v]>0)
{
map[i][v]--;
map[v][i]--;
Euler_circle_u(i);
}
path[pathnum++]=v;
}
int main(){
int f;
cin>>f;
memset(map,0,sizeof(map));
for (int i=0;i<f;i++)
{
int a,b;
cin>>a>>b;
minv=Min(a,minv);
minv=Min(b,minv);
maxv=Max(a,maxv);
maxv=Max(b,maxv);
map[a][0]++;
map[b][0]++;
map[a][b]++;
map[b][a]++;
}
int k=minv;
for (int i=minv;i<=maxv;i++)
if (map[i][0]%2==1)
{
k=i;
break;
}
Euler_circle_u(k);
for (int i=pathnum-1;i>=0;i--)
cout<<path[i]<<endl;
return 0;

骑马修栅栏--一种较为慢的做法