本文主要是介绍hihocode 第五十周 欧拉路·二，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目1 : 欧拉路·二
时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB
-
5 5 3 5 3 2 4 2 3 4 5 1
样例输出 -
1 5 3 4 2 3
描述
在上一回中小Hi和小Ho控制着主角收集了分散在各个木桥上的道具，这些道具其实是一块一块骨牌。
主角继续往前走，面前出现了一座石桥，石桥的尽头有一道火焰墙，似乎无法通过。
小Hi注意到在桥头有一张小纸片，于是控制主角捡起了这张纸片，只见上面写着：
将M块骨牌首尾相连放置于石桥的凹糟中，即可关闭火焰墙。切记骨牌需要数字相同才能连接。 ——By 无名的冒险者
小Hi和小Ho打开了主角的道具栏，发现主角恰好拥有M快骨牌。
小Ho：也就是说要把所有骨牌都放在凹槽中才能关闭火焰墙，数字相同是什么意思？
小Hi：你看，每一块骨牌两端各有一个数字，大概是只有当数字相同时才可以相连放置，比如：
小Ho：原来如此，那么我们先看看能不能把所有的骨牌连接起来吧。
提示：Fleury算法求欧拉路径
输入
第1行：2个正整数，N,M。分别表示骨牌上出现的最大数字和骨牌数量。1≤N≤1,000，1≤M≤5,000
第2..M+1行：每行2个整数，u,v。第i+1行表示第i块骨牌两端的数字(u,v)，1≤u,v≤N
输出
第1行：m+1个数字，表示骨牌首尾相连后的数字
比如骨牌连接的状态为(1,5)(5,3)(3,2)(2,4)(4,3)，则输出"1 5 3 2 4 3"
你可以输出任意一组合法的解。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 5010
#define MAXM 100010
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)using namespace std;int Read()
{char c = getchar();while (c < '0' || c > '9') c = getchar();int x = 0;while (c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();}return x;
}void Print(int a)
{if(a>9)Print(a/10);putchar(a%10+'0');
}struct Stack
{int top,node[MAXN];
}s;
int Edge[MAXN][MAXN];
int n;
void dfs(int x)
{s.top++;s.node[s.top]=x;for(int i=0;i<n;i++){if(Edge[i][x]>0){
// Edge[i][x]=0; Edge[x][i]=0; //删除此边Edge[i][x]--; Edge[x][i]--;//删除此边 数量减一dfs(i);break;}}
}void Fleury(int x)
{int i,b;s.top=0; s.node[s.top]=x;int flag=0;while(s.top>=0){b=0;for(i=0;i<n;i++){if(Edge[s.node[s.top]][i]>0){b=1; break;}}if(b==0){if(flag) printf(" ");flag=1;printf("%d",s.node[s.top]+1);s.top--;}else{s.top--;dfs(s.node[s.top+1]);}}puts("");
}int main()
{
// fread;int m;
// scanf("%d%d",&n,&m);while(scanf("%d%d",&n,&m)!=EOF){int deg,num,start;MEM(Edge,0);for(int i=0;i<m;i++){int s,t;scanf("%d%d",&s,&t);Edge[s-1][t-1]++;Edge[t-1][s-1]++; //数据中有重边 将标记改为边的数量}num=0; start=0;for(int i=0;i<n;i++){deg=0;for(int j=0;j<n;j++)deg+=Edge[i][j];if(deg%2==1){start=i;num++;}}if(num==0||num==2)Fleury(start);
// else puts("");}return 0;
}
这篇关于hihocode 第五十周 欧拉路·二的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
