Poj 1724 Roads(DFS 可行性剪枝 最优性剪枝 向量)

原创 2017年12月13日 20:06:34
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
using namespace std;

struct Roads
{
    int d;
    int l;
    int t;
};

vector<Roads> city[105];    //定义向量,相当于一个二维数组,其中第一维的长度无限大,第二维的长度是105,数组中的各个元素是之前定义的Roads结构体

int K,N,R;
int totallen,totalcost,minlen;
int minn[105][10005];    //minn[i][j]表示到达i城市且花费了j时所走的最小路程 ,用于下面每走到一个城市都可以进行剪枝
int visited[105];       //由于本题是求最短路径长度,而若是走的过程中,对一个城市走了不止一遍,那么肯定不再是最短路径长度,所以每一个城市都不可以重复走

void dfs( int c )
{
    if( c == N )   //走到了终点
        {
              minlen = min( minlen , totallen );  //结束递归之前,先更新minlen的值
           return ;
        }
    int rnum = city[c].size();
    for( int i = 0 ; i < rnum ; ++i )   //遍历c城市所能走的所有路
     {
          if( visited[city[c][i].d] || totalcost + city[c][i].t > K )   //可行性剪枝
            continue;
         if( totallen + city[c][i].l >= minlen || totallen + city[c][i].l >= minn[city[c][i].d][totalcost + city[c][i].t] )  //最优性剪枝    
             continue;
         totalcost += city[c][i].t;
         totallen += city[c][i].l;
         minn[city[c][i].d][totalcost] = totallen;
         visited[city[c][i].d] = 1;   //更新状态
         dfs(city[c][i].d);
         totallen -=  city[c][i].l;
         totalcost -= city[c][i].t;
         visited[city[c][i].d] = 0;   //还原状态
      }    
}


int main()
{
   freopen( "E:\\in.txt", "r" , stdin );
   cin >> K;   //总共的钱
   cin >> N >> R;
   for(int i = 0; i < R ; ++i)   //构建图(连接表)
      {
            int s;
            cin>>s;
            Roads r;
            cin>>r.d>>r.l>>r.t;
            city[s].push_back(r);
      }
   totalcost = 0;  //初始化
   totallen = 0;
   minlen = 1 << 30;
   for(int i = 0 ; i < 105 ; ++i)
       for(int j = 0 ; j < 10005 ; ++j)
            minn[i][j] = 1 << 30;
   memset(visited,0,sizeof(visited));
   dfs(1);    //深搜开始
   if(minlen == 1 << 30)    //minlen的值没有被改变 说明并没有找到合适的路
      cout << "-1" << endl;
   else
      cout << minlen << endl;
   return 0;   
}



POJ1724 ROADS(深搜DFS,最短路,dijkstra,用优先队列优化)

题目: ROADS Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 14825   Accepted:...
  • riba2534
  • riba2534
  • 2017年04月14日 14:50
  • 556

poj入门水题--深度搜索(dfs)题 1011,含各种剪枝,比较经典

深度搜索(dfs)题 1011,含各种剪枝,比较经典
  • qq_17246605
  • qq_17246605
  • 2016年12月25日 20:49
  • 830

DFS + 剪枝策略

一:简介 (1)相信做过ACM的人,都很熟悉图和树的深度优先搜索;算法里面有蛮力法 —— 就是暴力搜索(不加任何剪枝的搜索); (2)蛮力搜搜需要优化时,就是需要不停的剪枝,提前减少不必要的搜索路径,...
  • u010700335
  • u010700335
  • 2015年03月06日 09:29
  • 3833

POJ 1011 最小的木棒 (dfs+剪枝|| 搜索好题)

Description 乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度...
  • h1021456873
  • h1021456873
  • 2016年03月15日 00:36
  • 589

uva140_dfs(回溯)最优性剪枝

题解: 1.原书中已经说明,如果两个节点的带宽 >= 最小带宽,无论如何也不可能比原解更优,应该剪掉。2.注意此题读入的时候一定要按 字典序 存储,这样计算出的最小值才是符合要求的3.注意strto...
  • tt2767
  • tt2767
  • 2015年08月20日 08:53
  • 588

搜索DFS+BFS和剪枝问题

HUD 1010题意:输入一个n*m的迷宫,和一个T:可以在迷宫中生存的最大时间。S为起点,D为终点。并且,每个格子只能踩一次,且只能维持一秒,然后该块地板就会塌陷。所以你必须每秒走一步,且到D点时,...
  • Codeblocksm
  • Codeblocksm
  • 2015年08月02日 17:53
  • 195

砝码(01背包问题的DFS剪枝)

点击打开链接 砝 码 Description FJ有一架用来称牛的体重的天平。与之配套的是N(1 砝码按照它们质量的大小被排成一行。并且,这一行中从第3个砝码开始,每个砝码的质量至少等于前面两个砝...
  • Feynman1999
  • Feynman1999
  • 2017年05月03日 15:01
  • 387

Uva307 Sticks 【dfs+剪枝】【习题7-14】

dfs的搜索过程还是得灵活!剪枝是个问题!!!
  • GuoZLH
  • GuoZLH
  • 2017年02月19日 22:48
  • 247

poj 3009 dfs暴力解决最短路

题目就不粘了,题意是这样的:一个带网格的方格板,有两种方格,一种是白色的,一种是网状的。白色表示可以通过,用数字0表示,网状的表示障碍物不能通过,用数字1表示。起点和终点分别在两个白色的上面,分别用数...
  • vita_xu
  • vita_xu
  • 2015年02月06日 13:08
  • 772

杭电ACM1010(dfs+剪枝)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1010 题目大意:一只小狗被困在了一座迷宫中,迷宫有一个起点和一个终点,“X”代表墙,不能通行,“.”...
  • Runner__1
  • Runner__1
  • 2015年11月24日 11:41
  • 534
内容举报
返回顶部
收藏助手
不良信息举报
您举报文章:Poj 1724 Roads(DFS 可行性剪枝 最优性剪枝 向量)
举报原因:
原因补充:

(最多只允许输入30个字)