阅读原文
此题来自 \(CodeForces\) \(2013\) 年愚人节比赛的 \(F\) 题。（话说本题翻译也是我写的呢 \(hhhh\) ）
题目要求找一个\(n\)个点\(m\)条边的无向图的 \(Hamilton\) 路径。
但是，之所以它能成为愚人节比赛的压轴大戏，就是因为它的算法不可以凭空捏造，而是需要复原 \(Petya\) 所编写的程序。
样例中所给出的 \(Yes\) \(or\) \(No\) 也都是在 \(Petya\) 所编写的程序运行下的结果，而不是实际上是否存在\(Hamilton\) 路径。（这一点从样例 \(3\) 上应该能看出来）
由于本人太弱，见过的算法太少，不能观察出 \(Petya\) 的算法，只能借助出题人Gerald（有时打开较慢）话说小哥哥还挺好看的让比赛总出题人写的博客（有时打开较慢）来获得 \(Petya\) 的算法。
为了节省大家的时间， \(Petya\) 的算法（一种众所周知的错误贪心方法）如下：
1）将无向图存储为邻接表（删除所有自环和重边）。
2）按照点的度数从小到大排序（度数相等的按输入顺序排序）。
3）尝试所有可能的路径起点，并尝试按照相应的邻接表的顺序从当前点移动到尚未访问的点。
4）如果成功找到了一条 \(Hamilton\) 路径，则输出 \(Yes\) ，否则输出 \(No\) 。
那么，我们就可以开始还原 \(Petya\) 的算法啦，总时间复杂度为 \(O(n^3)\) 。
如有疑问，评论区或私信均可，我会尽快回复。
代码如下：
#include<bits/stdc++.h> using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int n,m,x,y,deg[25]; bool edge[25][25],vis[25]; int main() { n=read(); m=read(); for(register int i=1;i<=m;i++) { x=read(); y=read(); if(x==y) continue; if(edge[x][y]) continue; deg[x]++; deg[y]++; edge[x][y]=1; edge[y][x]=1; } for(register int i=1;i<=n;i++) { int st=i,j; memset(vis,0,sizeof(vis)); vis[st]=1; for(j=1;j<n;j++) { int minn=0,de=0; for(register int k=1;k<=n;k++) { if(edge[st][k]&&!vis[k]) { if(de==0||minn>deg[k]) { de=k; minn=deg[k]; } } } if(de==0) break; st=de; vis[st]=1; } if(j==n) { printf("Yes\n"); return 0; } } printf("No\n"); return 0; }转载于:https://www.cnblogs.com/Peter0701/p/11261173.html
相关资源：JAVA上百实例源码以及开源项目