题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3620
    这道题给了一个起点,一个终点,在有限的时间内,获得最大的财宝数。输入数据有房间数n、房间间的关系组数m、受限时间

,以及每个房间的财宝数,m组关系的具体情况。
    n最大是10,深搜完全可以。
    这个题需要注意以下几点:1、深搜的终点不是说到了终点就停止了,他还可以继续走下去,在允许的时间内转个圈回到终点。

所以要尽最大可能的利用时间。2、某个点走过了,还可以再次经过,再次经过的时候,那个房间的财宝数已经是0了,时间加倍,

当前财宝数不更新。3、回溯的时候,不要简单的把标记走过的房间变成0,而要回溯到上一步时房间的标记值,刚才在这纠结了半

天、、、
    我看有的人说这道题用状态压缩来做,厄,我是菜鸟,目前对状态压缩很模糊,只是按照自己的思路写代码实现了一下、、
代码如下:

#include <stdio.h>
#include<string.h>

#define MAX 15
#define INF 999999999

int map[MAX][MAX];
int vm[MAX][MAX];
int num[MAX];
int vn[MAX];
int n,t,sum;
int sn,en;

void DFS( int s,int whight,int time ){
    int pos;
    if( s == en  && time<=t ){
        if( whight > sum )
            sum = whight;
    }
    for(int i=0; i<n; i++){
        if( !vm[s][i] && map[s][i]!=INF && map[s][i]+time<=t  ){
            if( !vn[i] )                 //第一次经过房间i,加上房间i的财宝值
                whight = whight + num[i];
            pos = vn[i];                //记录这次搜索到前的搜索状态,以便回溯
            vn[i] = 1;
            vm[s][i] = 1;                 //走过的边标记
            DFS( i,whight,time+map[s][i] );       //搜索接下来的状态
            vn[i] = pos;            //回溯到上个状态点i的状态,而不是简单赋0
            vm[s][i] = 0;
            if( !vn[i] )
                whight = whight – num[i];
        }
    }
}

int main(){
    int u,v,w,m;
    int i,j;
    while( scanf("%d%d%d", &n,&m,&t) !=EOF ){
        scanf( "%d%d",&sn,&en );
        for( i=0; i<n; i++ ){
            scanf( "%d",&num[i] );
        }
        for( i=0; i<n; i++ )
            for(j=0; j<n; j++)
                map[i][j] = INF;
        for( i=0; i<m; i++ ){
            scanf("%d%d%d",&u,&v,&w);
            if( map[u][v] > w )
                map[u][v] = map[v][u] = w;    //注意:双向边
        }
        sum = 0;
        memset( vn, 0, sizeof(vn) );
        memset( vm, 0, sizeof(vm) );
        vn[sn] = 1;
        DFS(sn,num[sn],0);    //从起点开始搜索
        printf("%d\n",sum);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation