[SCOI2007 kshort]
求图的s-t第K短简单路问题,若有长度相同的,字典序小的优先。

首先,由于是简单路,所以A*是不能做的,因为有可能有两条s-i(i为某个中间点)路P1和P2,P1比P2短,但由于P1到达的顶点与P2不同,导致最终沿P1到达t的路径长度长于沿P2到达t的(甚至有可能沿P1根本到不了t)。然后,如果直接用DFS,由于要求的是第K优解,而不是最优解,所以不能使用最优性剪枝(包括分支限界),因此专门为最优性剪枝服务的“改变搜索顺序”技巧也不能使用了,因此,能够使用的只有可行性剪枝,而本题的数据范围使得这种算法必然TLE。

正解是一种由迭代加深思想扩展得到的“迭代变优”DFS。设置一个路径长度上限Z,搜索s到t的所有简单路,在搜索过程中,遇到长度大于Z的路径就停止(剪枝),然后,若得到路径不足K条,则增加Z的值,重新开始搜索,直到得到的路径总数大于等于K条为止。这里可以进行启发式的优化,设g[i]为点i到t的最短路长度,则搜索过程中,假设目前搜到点i,则(目前路径长度+g[i])是对整条路径最短长度的乐观估计,如果这个值超过了Z,就可以剪枝,但在剪枝之前要记下这个超过了Z的启发值,取其中最小的作为下一次迭代的Z值。那么对于字典序肿么办?可以在搜索过程中,强制先搜编号小的结点,这样得到的s-t路径必然是字典序递增的。另外只要求出第K条路径,搜索就可以终止,因为容易证明,题目要求的第K短的路径一定已经求出来了(只不过不一定是最后一条而已),找到即可。此外,在搜索过程中不要忘了可行性剪枝,就是如果沿目前搜到的路径已经到不了t了,剪枝。

“迭代变优”DFS,就是设置一个解的评价值的上限(最小值)或下限(最大值),在搜索过程中,如果实际评价值(或者启发值,如果可以加启发式优化的话)越过这个限制,则剪枝。在一次搜索后,如果没有得到符合要求的解,就将该限制值设为本次搜索过程中越界“越”得最近的那个值,重新开始搜索,直到找到所需要的解或者发现无解(如果一次搜索中没有发生越界,却仍然没有找到解)为止。其应用主要体现在两个方面:(1)搜索树过深甚至无限深,但所需求的那个解却不深的情况;(2)求第K优解的情况。

代码:
#include <iostream>
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
#include 
<algorithm>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
const int MAXN = 51, MAXK = 201, MAXM = 3000, INF = ~0U >> 2;
struct edge {
    
int a, b, w, pre, next;
} E[MAXM 
+ MAXN], E0[MAXM + MAXN];
struct edge0 {
    
int a, b, w;
    
bool operator< (edge0 e0) const {return b < e0.b;}
} _E[MAXM];
int n, m, s, t, K, dist[MAXN], Q[MAXN + 1];
int Z, Z0, vst0[MAXN], _FL, len0, X00[MAXN], No, len[MAXK], X0[MAXK][MAXN], sum0[MAXK], reslen, res[MAXN];
bool vst[MAXN], res_ex = 0;
void init_d()
{
    re(i, n) E[i].pre 
= E[i].next = E0[i].pre = E0[i].next = i; m = n;
}
void add_edge(int a, int b, int w)
{
    E[m].a 
= a; E[m].b = b; E[m].w = w; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m;
    E0[m].a 
= b; E0[m].b = a; E0[m].w = w; E0[m].pre = E0[b].pre; E0[m].next = b; E0[b].pre = m; E0[E0[m].pre].next = m++;
}
void init()
{
    
int m0; scanf("%d%d%d%d%d"&n, &m0, &K, &s, &t); init_d(); s--; t--;
    re(i, m0) {scanf(
"%d%d%d"&_E[i].a, &_E[i].b, &_E[i].w); _E[i].a--; _E[i].b--;}
    sort(_E, _E 
+ m0);
    re(i, m0) add_edge(_E[i].a, _E[i].b, _E[i].w);
}
void prepare()
{
    re(i, n) {vst[i] 
= 0; dist[i] = INF;} vst[t] = 1; dist[t] = 0; Q[0= t;
    
int x, y, d0, d1;
    
for (int front=0, rear=0!(!front && rear==|| front==rear+1); front==? front=0 : front++) {
        x 
= Q[front]; d0 = dist[x];
        
for (int p=E0[x].next; p != x; p=E0[p].next) {
            y 
= E0[p].b; d1 = d0 + E0[p].w;
            
if (d1 < dist[y]) {
                dist[y] 
= d1;
                
if (!vst[y]) {vst[y] = 1; Q[rear==? rear=0 : ++rear] = y;}
            }
        }
        vst[x] 
= 0;
    }
}
void dfs(int x, int sum)
{
    
if (x == t) {
        
if (sum <= Z) {sum0[No] = sum; len[No] = len0; re(i, len0) X0[No][i] = X00[i]; No++if (No == K) res_ex = 1;}
        
else if (sum < Z0) Z0 = sum;
        
return;
    } 
else {
        
int h0 = sum + dist[x];
        
if (h0 > Z) {if (h0 < Z0) Z0 = h0; return;}
        vst0[x] 
= ++_FL; Q[0= x; int _x, _y;
        
for (int front=0, rear=0; front<=rear; front++) {
            _x 
= Q[front];
            
for (int p=E[_x].next; p != _x; p=E[p].next) {
                _y 
= E[p].b;
                
if (!vst[_y] && vst0[_y] != _FL) {vst0[_y] = _FL; Q[++rear] = _y;}
            }
        }
        
if (vst0[t] != _FL) return;
        
for (int p=E[x].next; p != x; p=E[p].next) {
            _y 
= E[p].b;
            
if (!vst[_y]) {vst[_y] = 1; X00[len0++= _y; dfs(_y, sum + E[p].w); if (res_ex) returnelse {len0--; vst[_y] = 0;}}
        }
    }
}
void solve()
{
    Z 
= dist[s]; int No0 = 0; _FL = 0;
    
while (1) {
        Z0 
= INF; No = 0; re(i, n) {vst[i] = 0; vst0[i] = 0;}
        vst[s] 
= 1; len0 = 1; X00[0= s; dfs(s, 0);
        
if (res_ex) {
            No0 
= K - No0;
            re(i, K) 
if (sum0[i] == Z) {No0--if (!No0) {reslen = len[i]; re(j, len[i]) res[j] = X0[i][j];}}
            
break;
        } 
else if (Z0 == INF) breakelse {No0 = No; Z = Z0;}
    }
}
void pri()
{
    
if (res_ex) {
        printf(
"%d", res[0+ 1);
        re2(i, 
1, reslen) printf("-%d", res[i] + 1);
        puts(
"");
    } 
else puts("No");
}
int main()
{
    init();
    prepare();
    solve();
    pri();
    
return 0;
}



只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理