今天第一次带队打了次boss，发现满地图找boss实际上就是运筹学中管梅谷提出的中国邮递员问题：即在把地图中所有的边都走至少一遍的情况下，设计一个路线，使总距离最小。

　　首先，所有的所有的boss地图都是非负赋权图，各边长就是所包含的格子数。如果boss地图是欧拉环游图，即地图没有奇点或者只有2个奇点而且入口处就是其中之一的奇点，这时只要用Fleury算法算出图的欧拉环游圈就是最优路径。

　　c++的Fleury算法如下：
　　1#include
　　2#include
　　3
　　4
　　5struct stack
　　6{int top , node[210];} f; //顶点的堆栈
　　7
　　8int a[201][201]; //图的邻接矩阵
　　9
　　10int n;
　　11
　　12void dfs(int x) //图的深度优先遍历
　　13{
　　14int i;
　　15
　　16f.top ++; f.node[f.top] = x;
　　17
　　18for (i = 1; i <= n; i ++)
　　19
　　20 if (a[x] > 0)
　　21 {
　　22 a[x] = 0; a[x] = 0; //删除此边
　　23
　　24 dfs(i);
　　25
　　26 break;
　　27 }
　　28}
　　29
　　30void Euler(int x) //欧拉路算法
　　31{
　　32int i , b;
　　33
　　34f.top = 0; f.node[f.top] = x; //入栈
　　35
　　36while (f.top >= 0)
　　37{
　　38 b = 0;
　　39
　　40 for (i = 1; i <= n; i ++)
　　41 if (a[f.node[f.top]] > 0)
　　42 {b = 1; break;}
　　43
　　44 if (b == 0) //如果没有点可以扩展，输出并出栈
　　45 {
　　46 printf("%d " , f.node[f.top]);
　　47
　　48 f.top --;
　　49 }
　　50 else {f.top --; dfs(f.node[f.top+1]);} //如果有，就DFS
　　51 }
　　52}
　　53
　　54int main()
　　55{
　　56
　　57int m , s , t , num , i , j , start;
　　58
　　59 //input
　　60
　　61 scanf("%d %d" , &n , &m); //n顶点数 m边数
　　62
　　63 memset(a , 0 , sizeof(a));
　　64
　　65 for (i = 0; i < m; i ++)
　　66 {
　　67 scanf("%d %d" , &s , &t);
　　68 a[s][t] = 1; a[t][s] = 1;
　　69 }
　　70
　　71
　　72 //判断是否存在欧拉回路
　　73
　　74 s = 0; start = 1;
　　75
　　76 for (i = 1; i <= n; i ++)
　　77 {
　　78 num = 0;
　　79
　　80 for (j = 1; j <= n; j ++)
　　81 num += a[j];
　　82
　　83 if (num % 2 == 1)
　　84{start = i; s ++;}
　　85 }
　　86
　　87 if ((s == 0) || (s == 2))
　　88Euler(start);
　　89 else printf("No Euler path\n");
　　90
　　91 getchar(); getchar();
　　92 return 0;
　　93}

　　如果地图地图不是欧拉环游图，就用添加重复边的方法是之成为欧拉环游图，添加的重复边就是在找boss时需要重复走的边，其中重复边的起点和终点要分别是地图的奇点，而且2个奇点之间中重复边走的路径要用Dijkstra算法找出最
　　短路径，添完重复边后再用Fleury算法即可算出最优环游。
　　Dijkstra的算法实现如下：
　　#include

　　#define MaxNum 765432100

　　using namespace std;

　　ifstream fin("Dijkstra.in");

　　ofstream fout("Dijkstra.out");

　　int Map[501][501];

　　bool is_arrived[501];

　　int Dist[501],From[501],Stack[501];

　　int p,q,k,Path,Source,Vertex,Temp,SetCard;

.......

阅读全文：http://bbs.51wan.com/viewthread.php?tid=315015&extra=page%3D1