判断
用来存储路径
1.铲雪车
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
这题就是欧拉回路，但是直接求距离就行
#include<bits/stdc++.h> using namespace std; int main() { double x1,x2,y1,y2; cin>>x1>>y1; double sum=0; while(cin>>x1>>y1>>x2>>y2) { double dx=x2-x1,dy=y2-y1; sum+=sqrt(dx*dx+dy*dy)*2; } int m=round(sum/1000/20*60); int hour=m/60; m%=60; printf("%d:%02d\n",hour,m); return 0; }
2.欧拉回路
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
re了这题，暂时不知道哪里的问题
#include<bits/stdc++.h> using namespace std; const int N=1e5+10,M=4e5+10; int h[N],e[M],ne[M],idx; int n,m,type; int din[N],dout[N]; int cnt,ans[M]; bool used[M]; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u) { for(int &i=h[u];~i;)//加了个引用来优化，让i一直等于h[u] { if(used[i]) { i=ne[i];//删边 continue; } used[i]=true;//标记这条边用过了 if(type==1) used[i^1]=true;//标记反向边也用过了 int t; if(type==1) { t=i/2+1; if(i&1) t=-t; } else t=i+1; int j=e[i];//先得到这条边 i=ne[i];//删除这条边 dfs(j);//遍历这条边 ans[++cnt]=t;//把这个路径存下来 } } int main() { scanf("%d",&type); scanf("%d%d",&n,&m); memset(h,-1,sizeof h); for(int i=0;i<m;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); if(type==1) add(b,a); dout[a]++,din[b]++; } if(type==1) { for(int i=1;i<=n;i++) if(din[i]+dout[i]&1)//假如无向边且是奇数，说明无欧拉回路 { puts("NO"); return 0; } } else { for(int i=1;i<=n;i++) if(din[i]!=dout[i])//假如有向图并且入度不等于出度，说明也无欧拉回路 { puts("NO"); return 0; } } for(int i=1;i<=n;i++) if(h[i]!=-1)//从有边的节点开始遍历 { dfs(i); break; } if(cnt<m)//假如最后的边数不等于m，说明也不存在 { puts("NO"); return 0; } puts("YES"); for(int i=cnt;i;i--) printf("%d ",ans[i]);//输出答案 puts(""); return 0; }
3.骑马修栅栏
题目意思就是从一个点出发经过每条边一次，就是欧拉路径，然后输出按照字典序最小的情况输出
字典序最小只要dfs扩展领边的时候从小到达dfs即可
这题不用删边进行优化，n比较小直接领接矩阵存进行
#include<bits/stdc++.h> using namespace std; const int N=510,M=1030; int g[N][N]; int n=500,m; int d[N]; int cnt,ans[M]; void dfs(int u) { for(int i=1;i<=n;i++)//从小到大枚举所有边 if(g[u][i])//假如右边，则更新 { g[u][i]--,g[i][u]--;//删除该边 dfs(i);//遍历这个点 } ans[++cnt]=u;//加路径加到答案里 } int main() { scanf("%d",&m); while(m--) { int a,b; scanf("%d%d",&a,&b); g[a][b]++,g[b][a]++;//两边方向的边都+1 d[a]++,d[b]++;//度数也加1 } int start=0; while(!d[start]) start++;//找起点，就是度数不为0的点 for(int i=1;i<=n;i++)//假如有度数为奇数的点，这个点就是起点 if(d[i]&1) { start=i; break; } dfs(start);//开始遍历 for(int i=cnt;i;i--) printf("%d\n",ans[i]);//输出答案 return 0; }
这题不用删边进行优化，n比较小直接领接矩阵存进行
#include<bits/stdc++.h> using namespace std; const int N=510,M=1030; int g[N][N]; int n=500,m; int d[N]; int cnt,ans[M]; void dfs(int u) { for(int i=1;i<=n;i++)//从小到大枚举所有边 if(g[u][i])//假如右边，则更新 { g[u][i]--,g[i][u]--;//删除该边 dfs(i);//遍历这个点 } ans[++cnt]=u;//加路径加到答案里 } int main() { scanf("%d",&m); while(m--) { int a,b; scanf("%d%d",&a,&b); g[a][b]++,g[b][a]++;//两边方向的边都+1 d[a]++,d[b]++;//度数也加1 } int start=0; while(!d[start]) start++;//找起点，就是度数不为0的点 for(int i=1;i<=n;i++)//假如有度数为奇数的点，这个点就是起点 if(d[i]&1) { start=i; break; } dfs(start);//开始遍历 for(int i=cnt;i;i--) printf("%d\n",ans[i]);//输出答案 return 0; }
4.单词游戏
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
把每个单词开头第一个字母和最后一个字母连起来，看成一条边，然后就是问有向图中是否存在欧拉路径
#include<bits/stdc++.h> using namespace std; const int N=30; bool st[N]; int din[N],dout[N],p[N]; int n; int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { char str[1010]; int T; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(st,0,sizeof st);//清空 memset(din,0,sizeof din);//清空 memset(dout,0,sizeof dout);//清空 for(int i=0;i<26;i++) p[i]=i;//初始化 while(n--) { scanf("%s",str); int len=strlen(str); int a=str[0]-'a',b=str[len-1]-'a'; st[a]=st[b]=true; din[b]++,dout[a]++; p[find(a)]=find(b);//并查集合并操作 } bool f=true; int start=0,end=0; for(int i=0;i<26;i++)//判断欧拉路径 if(din[i]!=dout[i]) { if(din[i]==dout[i]+1) end++; else if(din[i]+1==dout[i]) start++; else//反之不存在欧拉路径 { f=false; break; } } if(f&&!(!start&&!end||start==1&&end==1)) f=false;//假如开头和结尾不是0或者1个说明不存在欧拉路径 int rep=-1; for(int i=0;i<26;i++)//做一遍并查集 if(st[i])//从有的点出发 { if(rep==-1) rep=find(i); else if(rep!=find(i))//假如有孤立点 { f=false; break; } } if(f) puts("Ordering is possible."); else puts("The door cannot be opened."); } return 0; }
