題干：

考慮一個包含 N 個頂點的無向圖，編號從 1 到 N，并包含 M 條邊。編號為 1 的頂點對應了一個礦藏，可從中提取珍稀的礦石。編號為 N 的頂點對應了一個礦石加工廠。每條邊有相應的通行時間 (以時間單位計)，以及相應的運載量 (以礦石單位計)。現決定使用一條路徑，將從礦藏中提取的礦石運送到加工廠。這條路徑應當具有盡可能高的運載量，以便并行運輸盡可能多的礦石。路徑的運載量等于它的各邊的最小運載量。然而，這些礦石很敏感，一旦從礦藏中提取出來，就會在 T 個時間單位之后開始分解，除非在這個時間截止之前到達工廠。因此，所選路徑的總通行時間 (各條邊的通行時間之和) 應當小于或等于 T。

輸入

輸入的第 1 行包含一個整數 X，表示測試數據的組數。

對于每組測試數據，第 1 行包含了以空格分隔的三個整數：N (2 ≤ N ≤ 10000)，M (1 ≤ M ≤ 50000) 和 T (1 ≤ T ≤ 500000)。接下來的 M 行，每行包含以空格分隔的四個整數：A, B, C, D，表示頂點 A 和 B 之間有一條邊，邊的運載量是 C (1 ≤ C ≤ 2×10^9)，邊的通行時間是 D (1 ≤ D ≤ 50000)。A 和 B 是介于 1 到 N 之間的不同整數。任意兩個頂點之間，至多有一條邊。

輸出

對于每組測試數據，在一行里輸出從礦藏到工廠的路徑的最大運載量，考慮到通行時間的約束。在滿足通行時間約束的條件下，礦藏和工廠之間總是存在至少一條路徑。

示例輸入

2
2 1 10
1 2 13 10
4 4 20
1 2 1000 15
2 4 999 6
1 3 100 15
3 4 99 4

示例輸出

13
99

解題報告：

? 題目不難，給定一個T，求起點到終點的在時間T內的 能夠裝載的最大礦石。二分這個裝載數+最短路check就行了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; const int INF = 0x3f3f3f3f; struct Edge {int to,ne,w,zzl;//裝載量 } e[MAX]; int tot,n,m,T; int head[MAX],dis[MAX],vis[MAX]; struct Point {int pos;int c;Point(){}Point(int pos,int c):pos(pos),c(c){}bool operator<(const Point b)const{return c > b.c;} }; void add(int u,int v,int w,int zzl) {e[++tot].to = v;e[tot].w = w;e[tot].zzl=zzl;e[tot].ne = head[u];head[u] = tot; } int Dijkstra(int x) {for(int i = 1; i<=n; i++) dis[i] = INF,vis[i] = 0;dis[1]=0;priority_queue<Point> pq;pq.push(Point(1,0));while(!pq.empty()) {Point cur = pq.top();pq.pop();if(vis[cur.pos]) continue;vis[cur.pos] = 1;for(int i = head[cur.pos]; ~i; i = e[i].ne) {int v = e[i].to;if(vis[v]) continue;if(e[i].zzl < x) continue;if(dis[v] > dis[cur.pos] + e[i].w) {dis[v] = dis[cur.pos] + e[i].w;pq.push(Point(v,dis[v]));}}}return dis[n]; } int main() {int t;cin>>t;while(t--) {scanf("%d%d%d",&n,&m,&T);tot=0;int l = INF,r = 0,mid,ans;for(int i = 1; i<=n; i++) head[i] = -1;for(int a,b,c,d,i = 1; i<=m; i++) {scanf("%d%d%d%d",&a,&b,&c,&d);add(a,b,d,c);add(b,a,d,c);r = max(r,c);l = min(l,c);}while(l<=r) {mid = (l+r)>>1;if(Dijkstra(mid) <= T) ans = mid,l = mid+1;else r = mid-1; }printf("%d\n",ans);}return 0 ; }

?

總結

以上是生活随笔為你收集整理的【HDU - 1839】Delay Constrained Maximum Capacity Path（最短路 + 二分）的全部內容，希望文章能夠幫你解決所遇到的問題。

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