首页 > 代码库 > 【ZJOI2006】【BZOJ1003】物流运输

【ZJOI2006】【BZOJ1003】物流运输

2024-08-14 20:04:31   218人阅读

其实这道题挺简单的，然而理解错题意导致近几个月都没做出来QAQ

原题：

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

1<=n<=100，1<=m<=20

 

这道题的意思是说有m个码头，每天从1跑到m，要跑n天（n次），我理解成从1跑到m要跑n天，然后根本没法做嘛qaq

理解题意就好办了，因为数据量很小，所以只需要暴力记录从第i天到第j天都能用的码头，SPFA一下花费，然后DP一下即可

状态方程大概是酱紫：f[i]=min(f[i],dis[j+1][i]*(j-i)+money)，dis是SPFA跑的最短路↑，也就是第i到j天的最小花费

有两点需要注意：

最后的答案要减一次改航线的花费，因为第一次选择航线不用花钱

最后DP的时候要先判断一下dis[j+1][i]是不是+oo，因为如果是+oo的话很有可能乘个(j-i)就爆了

代码：

技术分享
 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 struct ddd{int next,y,value;}e[210000];int LINK[110000],ltop=0; 8 inline void insert(int x,int y,int z){e[++ltop].next=LINK[x];LINK[x]=ltop;e[ltop].y=y;e[ltop].value=http://www.mamicode.com/z;} 9 int t,n,money,m;10 bool jin[30][110],can[30];11 int dis[110][110],disf[30];12 int dui[110000],tou=0;13 bool visited[30];14 int f[110];15 void get_cant(int x,int y){16     for(int i=1;i<=n;i++){17         can[i]=true;18         for(int j=x;j<=y;j++)19             if(jin[i][j]){  can[i]=false;  break;}20     }21 }22 void SPFA(int x,int y){23     memset(visited,0,sizeof(visited));24     memset(disf,10,sizeof(disf));25     dui[tou=1]=1;  disf[1]=0;26     for(int k=1;k<=tou;k++){27         visited[dui[k]]=false;28         for(int i=LINK[dui[k]];i;i=e[i].next)if(can[e[i].y])29             if(disf[dui[k]]+e[i].value<disf[e[i].y]){30                 disf[e[i].y]=disf[dui[k]]+e[i].value;31                 if(!visited[e[i].y]){  visited[e[i].y]=true;  dui[++tou]=e[i].y;}32             }33     }34     dis[x][y]=disf[n];35 }36 int main(){37     //freopen("ddd.in","r",stdin);38     //freopen("ddd.out","w",stdout);39     //freopen("bzoj_1003.in","r",stdin);40     //freopen("bzoj_1003.out","w",stdout);41     memset(can,0,sizeof(can));42     memset(f,10,sizeof(f));43     cin>>t>>n>>money>>m;44     int _left,_right,_value;45     while(m --> 0){//趋向于46         scanf("%d%d%d",&_left,&_right,&_value);47         insert(_left,_right,_value),insert(_right,_left,_value);48     }49     cin>>m;50     while(m --> 0){//趋向于51         scanf("%d%d%d",&_value,&_left,&_right);52         for(int i=_left;i<=_right;i++)53             jin[_value][i]=true;54     }55     for(int i=1;i<=t;i++)56         for(int j=i;j<=t;j++){57             get_cant(i,j);58             SPFA(i,j);59         }60     f[0]=0;61     for(int i=1;i<=t;i++)62         for(int j=0;j<i;j++)if(dis[j+1][i]<168430090)//防止下面乘(i-j)的时候爆掉63             f[i]=min(f[i],f[j]+dis[j+1][i]*(i-j)+money);//注意这里是j+1，因为从变的第二天才开始跑这种方案64     cout<<f[t]-money<<endl;//第一次走的航道不用花钱65     return 0;66 }
View Code

 

【ZJOI2006】【BZOJ1003】物流运输


联系
我们