Delivery Delays

題意

$1000$個點,$5000$條邊的無向圖,披薩店在$1$號店.$1000$份披薩訂單,每個訂單有下單時間,送達地點,披薩制作出來的時間.你是快遞員初始在$1$號點,每次可以拿無窮多披薩,送完以后返回$1$號點繼續送,送餐的時候要求按照下單順序送達,求等待時間最長的顧客的最小等待時間.

題解

其實這道題不難,讀題的時候讀漏了一個條件…然后就GG了.

最小化最大值的問題,我們可以思考二分答案再check的套路進行.

二分等待時間最長的顧客的等待時間$M$,則其他所有顧客的等待時間不應超過$M$.

如何$check$呢?

答:我們可以用$dp$的方法進行$check$.

考慮到所有的披薩都必須按照下單時間順序送達,那么可以想象到最優的方案應該會將披薩序列分成若干小段,每一段都是從$1$號點出發,拿上該段所有的披薩,然后以最短路的形式,依次將披薩送達,最后回道$1$點.

那么我們就可以定義$dp[i]$表示將前$i$塊披薩準時送達,且最后回到$1$點出所花費的最小時間.

轉移方程是$O(n)$的

對于$i$這個點,將所有$j\ge i+1$的$dp[j]$全部更新.

定義$len[i][j]$表示從$1$出發,依次經過$i$,$i+1$,…,$j$這些點的最短路徑長度.

當用$dp[i]$來更新$dp[j]$的時候

我們注意到出發時間一定不能小于$max\{dp[i],t[i+1],t[i+2],...,t[j]\}$,因為必須等這些披薩都制作完成后才能觸出發

并且出發時間也一定不能大于$min\{M+s[i+1]?len[i][i+1],...,M+s[j]?len[i][j]\}$.
因為對于每個$t$,滿足$i+1\le t\le j$,必然有$len[i][t]+st?s[j]\le M$,也即$st\le M?len[i][t]+s[j]$

同時滿足這兩個條件的$j$才能由$i$進行轉移.

如果最后$dp[k]$被更新過,那么限制$M$就是可星的,否則布星.

代碼

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <queue> #define pr(x) std::cout << #x << ':' << x << std::endl #define rep(i,a,b) for(int i = a;i <= b;++i) const int N = 1007; typedef long long LL; const LL inf = 1e15; typedef std::pair<LL,int> pii; std::vector<pii> edge[N]; LL dis[N][N],dp[N]; void Dij(LL D[N],int s) {rep(i,0,N-1) D[i] = inf;std::priority_queue<pii,std::vector<pii>,std::greater<pii> > Q;D[s] = 0;Q.push((pii){D[s],s});while(!Q.empty()) {pii p = Q.top();Q.pop();int u = p.second;if(D[u] < p.first) continue;for(pii e : edge[u]) {int v = e.second;LL c = e.first;if(D[v] > D[u] + c) {D[v] = D[u] + c;Q.push((pii){D[v],v});}}} } LL s[N],t[N],u[N]; int n,m,k; bool check(LL M) {dp[0] = 0;rep(i,1,k) dp[i] = inf;rep(i,0,k-1) {LL st = dp[i],len = 0,mxst = inf;rep(j,i+1,k) {if(j == i+1) len += dis[1][u[i+1]];else len += dis[u[j-1]][u[j]];st = std::max(st,t[j]);//離開1號點的時間mxst = std::min(mxst,M-len+s[j]);LL wait = st+len-s[j];//當前點等待時間if(wait <= M && st <= mxst) dp[j] = std::min(dp[j],st+len+dis[u[j]][1]);else break;}}return dp[k] < inf; } int main() {std::ios::sync_with_stdio(false);std::cin >> n >> m;rep(i,1,m) {int a,b;LL c;std::cin >> a >> b >> c;edge[a].push_back((pii){c,b});edge[b].push_back((pii){c,a});}rep(i,1,n) {Dij(dis[i],i);}std::cin >> k;rep(i,1,k) {std::cin >> s[i] >> u[i] >> t[i];}LL l = 0,r = inf;while(r > l) {LL mid = (l + r) >> 1;if(check(mid)) r = mid;else l = mid + 1;}std::cout << l << std::endl; }

總結

以上是生活随笔為你收集整理的NCPC2018 D.Delivery Delays[二分答案+DP check]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。