题目链接: https://vjudge.net/problem/HDU-2181
题意: 一个规则的实心十二面体, 它的 20 个顶点标出世界著名的 20 个城市, 你从一个城市出发经过每个城市刚好一次后回到出发的城市.
思路: dfs 和回溯, 算一个基础题吧, 这里需要邻接矩阵, 用 bool 就可以, 也可以用 vector, 数据小, 就用前者了
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <queue>
- #include <vector>
- #include <string>
- using namespace std;
- #define inf (1LL <<31) - 1
- #define rep(i,j,k) for(int i = j; i <= (k); i++)
- #define rep__(i,j,k) for(int i = j; i < (k); i++)
- #define per___(i,j,k) for(int i = j; i> (k); i--)
- #define per(i,j,k) for(int i = j; i>= (k); i--)
- const int N = 30;
- bool mp[N][N]; // 邻接矩阵
- int in;
- bool vis[N]; // 记录拜访过的城市, 每个 dfs 的分支都需要一次初始化
- int ans;
- struct node{
- int way[N]; // 记录路线
- int l; // 长度
- node(int a = 0){ l = a; }
- };
- void input(){
- memset(mp, false, sizeof(mp));
- int a, b, c;
- rep(i, 1, 20){
- cin>> a>> b>> c;
- mp[i][a] = mp[i][b] = mp[i][c] = true; // 能到达的为 true
- }
- }
- void dfs(int now,node& rec){
- // 拜访了所有的城市
- if (rec.l == 20){
- // 拜访的最后一个城市能不能回到初始城市
- if (!mp[now][in]) return;
- // 可以, 输出答案
- cout <<(++ans) << ":";
- rep__(i, 0, rec.l) cout << " " << rec.way[i];
- cout << " " << in << endl;
- return;
- }
- rep(i, 1, 20){
- // 从小到大遍历城市编号, 解决了字典序
- // 能到, 没被拜访过
- if (mp[now][i] == true && !vis[i]){
- vis[i] = true;
- rec.way[rec.l++] = i;
- dfs(i, rec);
- vis[i] = false;//(1)
- rec.l--; //(2) (1)(2) 回溯
- }
- }
- }
- int main(){
- input();
- node rec;
- while (cin>> in && in != 0){
- rec.way[rec.l++] = in; // 记录开始的城市
- vis[in] = true; // 标记已经拜访过的城市
- ans = 0;
- dfs(in,rec);
- rec.l = 0; //(1)
- vis[in] = false; //(2) (1)(2) 回溯
- }
- return 0;
- }
, 直接看代码吧, 写的比较详细
来源: http://www.bubuko.com/infodetail-3119295.html