大体题意：
要求从1号出发，一笔画经过所有的路，问是否有解，并打印字典序最小的解？
思路：
显然是无向图的欧拉道路！
先判连通，直接用并查集了，不连通直接-1了
连通的话，在看看每个点的度数，当奇点的个数不是0 并且不是2 肯定是-1
如果是2 的话，1号结点是偶数度数的话也是-1
否则我们就可以从1号结点直接dfs找路了！
注意：
不能再dfs之前就输出路径，这样是不对的 = = 这样只得了20分！
因为这个点可能不合适，因此我们要用的stack 最后输出stack即可！
详细见代码：
#include
#include
#include
#include
#define mr make_pair
#include
using namespace std;
const int maxn = 10001;
bool g[maxn][maxn];
int n,m;
int num[10001];
bool vis[maxn][maxn];
vectorG[maxn];
int fa[maxn];
stacksk;
int find(int x){
return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}
void add(int x,int y){
int xx = find(x);
int yy = find(y);
if (xx != yy)fa[yy] = xx;
}
void dfs(int k){
int len = G[k].size();
for (int i = 0; i 问题描述
|
试题编号： |
201512-4 |
|
试题名称： |
送货 |
|
时间限制： |
1.0s |
|
内存限制： |
256.0MB |
|
问题描述： |
问题描述 为了增加公司收入，F公司新开设了物流业务。由于F公司在业界的良好口碑，物流业务一开通即受到了消费者的欢迎，物流业务马上遍及了城市的每条街道。然而，F公司现在只安排了小明一个人负责所有街道的服务。 输入格式 输入的第一行包含两个整数n, m，表示交叉路口的数量和街道的数量，交叉路口从1到n标号。 输出格式 如果小明可以经过每条街道正好一次，则输出一行包含m+1个整数p 1, p 2, p 3, …, p m+1，表示小明经过的路口的顺序，相邻两个整数之间用一个空格分隔。如果有多种方案满足条件，则输出字典序最小的一种方案，即首先保证p 1最小，p 1最小的前提下再保证p 2最小，依此类推。 样例输入 4 5 样例输出 1 2 4 1 3 4 样例说明 城市的地图和小明的路径如下图所示。 样例输入 4 6 样例输出 -1 样例说明 城市的地图如下图所示，不存在满足条件的路径。 评测用例规模与约定 前30%的评测用例满足：1 ≤ n ≤ 10, n-1 ≤ m ≤ 20。 |
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net
最佳实践：路径路由匹配规则的设计与实现 作者：哲思 时间：2023.5.9 邮箱：zhe__si@163.com GitHub：zhe-si (哲思) (github.com) 前言 时间一晃研究生都过去大半年了，学了些东西，也做了些项目，借着博客总结一下。这…
