[ZJOI2006]物流运输题解

[ZJOI2006]物流运输

时间限制: 10 Sec 内存限制: 162 MB

题目描述

　　物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转
停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种
因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是
修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本
尽可能地小。

输入

　　第一行是四个整数n（1<=n<=100）、m（1<=m<=20）、K和e。n表示货物运输所需天数，m表示码头总数，K表示
每次修改运输路线所需成本。接下来e行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编
号以及航线长度（>0）。其中码头A编号为1，码头B编号为m。单位长度的运输费用为1。航线是双向的。再接下来
一行是一个整数d，后面的d行每行是三个整数P（ 1 < P < m）、a、b（1< = a < = b < = n）。表示编号为P的码
头从第a天到第b天无法装卸货物（含头尾）。同一个码头有可能在多个时间段内不可用。但任何时间都存在至少一
条从码头A到码头B的运输路线。

输出

　　包括了一个整数表示最小的总成本。总成本=n天运输路线长度之和+K*改变运输路线的次数。

样例输入

样例输出

32
//前三天走1-4-5，后两天走1-3-5，这样总成本为(2+2)*3+(3+2)*2+10=32
　这道题我是拿状压做的，虽然慢了点，但是能抓到老鼠的就是好猫。
　因为m<=20，且1，m,不受限制所以可以说m<=18这样状压就妥妥的了。我们完全可以先预处理出来在那些点能用的情况下1~m的最短路，然后将所有可行解建一个链表，缩短时间，然后再算出来每一天那些码头不能用，然后传统DP就好了。

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<map>
  7 #include<queue>
  8 #include<string>
  9 #include<cmath>
 10 using namespace std;
 11 int t,n,m,k,zz,d;
 12 struct ro{
 13     int to,l;
 14     int next;
 15 }road[1000];
 16 int a[40];
 17 void build(int x,int y,int z){
 18     zz++;
 19     road[zz].to=y;
 20     road[zz].next=a[x];
 21     road[zz].l=z;
 22     a[x]=zz;
 23 }
 24 int dis[(1<<18)+5][21];
 25 int q[200],zt[105],head,en;
 26 bool rd[200];
 27 bool yx;
 28 int pre[(1<<18)+5];
 29 bool spfa(int tt){
 30     memset(q,0,sizeof(q));
 31     head=1,en=0;
 32     dis[tt][1]=0;
 33     rd[1]=1;
 34     en++;
 35     q[en]=1;
 36     while(en>=head)
 37     {
 38         int x=q[head];
 39         head++;
 40         rd[x]=0;
 41         for(int i=a[x];i>0;i=road[i].next)
 42         {
 43          
 44             int y=road[i].to;
 45             if(y==n||(1<<(y-2)&tt))
 46             {
 47                 if(dis[tt][y]>dis[tt][x]+road[i].l)
 48                 {
 49                     dis[tt][y]=dis[tt][x]+road[i].l;
 50                     if(!rd[y])
 51                     {
 52                         rd[y]=1;
 53                         en++;
 54                         q[en]=y;
 55                     }
 56                 }
 57             }
 58         }
 59     }
 60     if(dis[tt][n]!=dis[tt][0])
 61         return 1;
 62     return 0;
 63 }
 64 int f[2][(1<<18)+5];
 65 int main(){
 66     memset(pre,-1,sizeof(pre));
 67     memset(dis,0x3f,sizeof(dis));
 68     scanf("%d%d%d%d",&t,&n,&k,&m);
 69     for(int i=1;i<=m;i++)
 70     {
 71         int x,y,z;
 72         scanf("%d%d%d",&x,&y,&z);
 73         build(x,y,z);
 74         build(y,x,z);
 75     }
 76     int lla=0;;
 77     for(int i=0;i<(1<<(n-2));i++)
 78     {
 79         if(spfa(i))
 80         {
 81             if(i==0) yx=1;
 82             pre[lla]=i;
 83             lla=i;
 84         }
 85     }
 86     scanf("%d",&d);
 87     for(int i=1;i<=d;i++)
 88     {
 89         int x,y,z;
 90         scanf("%d%d%d",&x,&y,&z);
 91         for(int j=y;j<=z;j++)
 92             zt[j]|=(1<<(x-2));
 93     }
 94     int la=1,now=0,mn=-k;
 95     for(int i=1;i<=t;i++)
 96     {
 97         swap(la,now);
 98         int mn2=0x7fffffff;
 99         for(int j=0;j!=-1;j=pre[j])
100         {
101             if((j&zt[i])||((!yx)&&j==0)) continue;
102             if(f[la][j])
103             {
104                 f[now][j]=min(f[la][j]+dis[j][n],mn+k+dis[j][n]);
105                 mn2=min(mn2,f[now][j]);
106             }
107             else
108             {
109                 f[now][j]=mn+k+dis[j][n];
110                 mn2=min(mn2,f[now][j]);
111             }
112         }
113         memset(f[la],0,sizeof(f[la]));
114         mn=mn2;
115     }
116     printf("%d
",mn);
117     //while(1);
118     return 0;
119 }

View Code