hdu 1839 Delay Constrained Maximum Capacity Path 二分+最短路

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=1839

题意:

有N个点，点1为珍贵矿物的采矿区，点N为加工厂，有M条双向连通的边连接这些点。走每条边的运输容量为C，运送时间为D。
他们要选择一条从1到N的路径运输，这条路径的运输总时间要在T之内，在这个前提之下，要让这条路径的运输容量尽可能地大。
一条路径的运输容量取决与这条路径中的运输容量最小的那条边。

题解:

二分cap，最短路判断

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 
18 int n,m,t;
19 ll c[maxn];
20 
21 struct node{
22     ll v,c,d;
23     node(ll v=0,ll c=0,ll d=0) : v(v),c(c),d(d) {}
24 };
25 vector<node> E[maxn];
26 
27 int inq[maxn],td[maxn];
28 
29 ll check(ll c){
30     for(int i=0; i<=n; i++) inq[i] = 0;
31     for(int i=0; i<=n; i++) td[i] = INF;
32     queue<int> q;
33     q.push(1),td[1]=0,inq[1]=1;
34 
35     while(!q.empty()){
36         int now = q.front();
37         q.pop(),inq[now]=0;
38         for(int i=0; i<(int)E[now].size(); i++){
39             node e = E[now][i];
40             ll v = e.v, cc = e.c, d = e.d;
41             if(td[v] > td[now]+d && cc >= c){
42                 td[v] = td[now]+d;
43                 if(inq[v]) continue;
44                 inq[v] = 1;
45                 q.push(v);
46             }
47         }
48     }
49 
50     return td[n];
51 }
52 
53 int main(){
54     int T = read();
55     while(T--){
56         scanf("%d%d%d",&n,&m,&t);
57         for(int i=0; i<=n; i++) E[i].clear();
58         MS(c);
59         for(int i=0; i<m; i++){
60             ll u,v,d; scanf("%I64d%I64d%I64d%I64d",&u,&v,&c[i],&d);
61             E[u].push_back(node{v,c[i],d});
62             E[v].push_back(node{u,c[i],d});
63         }
64 
65         sort(c,c+m);
66 
67         int l=0,r=m-1,ans;
68         while(l<=r){
69             int mid = (l+r)/2;
70             int tmp = c[mid];
71             if(check(tmp) <= t){
72                 ans = tmp;
73                 l = mid+1;
74             }else{
75                 r = mid-1;
76             }
77         }
78         cout << ans << endl;
79     }
80 
81     return 0;
82 }