UVA208Firetruck 消防车（图的路径搜索）

题意：输入一个n(n20)个节点的无向图以及某个结点k，按照字典序从小到大顺序输出从结点1到结点k的所有路径，要求经过结点不能重复经过。

分析：终于做到水题了，此题唯一要点就是先判断是否能到达，用dfs。

#include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<iostream> #include<vector> #include<list> #include<set> using namespace std; const int maxn = 20+5; int G[maxn][maxn], vis[maxn]; int k,m; int allroute; int routemap[400][maxn]; void solve(int cur,int dep) {if (cur == k) {for (int i = 0; i < dep-1; i++) {cout << routemap[allroute][i] << " ";}cout << routemap[allroute][dep - 1];cout << endl;allroute++;memcpy(routemap[allroute], routemap[allroute - 1], sizeof(routemap[allroute - 1]));return;}for (int i = 1; i <= m; i++) {if (G[cur][i]&&!vis[i]) {vis[i] = 1;routemap[allroute][dep] = i;solve(i, dep + 1);vis[i] = 0;}} } bool isarrive(int cur) {if (cur == k) {return true;}for (int i = 1; i <= m; i++) {if (G[cur][i] && !vis[i]) {vis[i] = 1;if (isarrive(i))return true;}}return false; } int main() {int a, b; int kase = 0;while (cin >> k && k) {++kase;memset(G, 0, sizeof(G));memset(vis, 0, sizeof(vis));m = 0; allroute = 0;while (cin >> a >> b && a&&b) {G[a][b] = 1;G[b][a] = 1;m = max(max(a, b), m);}cout << "CASE " << kase << ":" << endl;if (isarrive(1)) {memset(vis, 0, sizeof(vis));vis[1] = 1;routemap[allroute][0] = 1;solve(1, 1);cout << "There are "<<allroute<< " routes from the firestation to streetcorner " << k << "." << endl;}else {//不可达cout << "There are 0 routes from the firestation to streetcorner " << k << "." << endl;}}//system("pause");return 0; }

 

总结

以上是生活随笔为你收集整理的UVA208Firetruck 消防车（图的路径搜索）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。