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

2019-11-06 07:11:35

字体：大中小

来源：转载

供稿：网友

题目链接:

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

题意:

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

题解:

二分cap，最短路判断

代码:

#include <bits/stdc++.h>using namespace std;typedef long long ll;#define MS(a) memset(a,0,sizeof(a))#define MP make_pair#define PB push_backconst int INF = 0x3f3f3f3f;const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}//////////////////////////////////////////////////////////////////////////const int maxn = 1e5+10;int n,m,t;ll c[maxn];struct node{ ll v,c,d; node(ll v=0,ll c=0,ll d=0) : v(v),c(c),d(d) {}};vector<node> E[maxn];int inq[maxn],td[maxn];ll check(ll c){ for(int i=0; i<=n; i++) inq[i] = 0; for(int i=0; i<=n; i++) td[i] = INF; queue<int> q; q.push(1),td[1]=0,inq[1]=1; while(!q.empty()){ int now = q.front(); q.pop(),inq[now]=0; for(int i=0; i<(int)E[now].size(); i++){ node e = E[now][i]; ll v = e.v, cc = e.c, d = e.d; if(td[v] > td[now]+d && cc >= c){ td[v] = td[now]+d; if(inq[v]) continue; inq[v] = 1; q.push(v); } } } return td[n];}int main(){ int T = read(); while(T--){ scanf("%d%d%d",&n,&m,&t); for(int i=0; i<=n; i++) E[i].clear(); MS(c); for(int i=0; i<m; i++){ ll u,v,d; scanf("%I64d%I64d%I64d%I64d",&u,&v,&c[i],&d); E[u].push_back(node{v,c[i],d}); E[v].push_back(node{u,c[i],d}); } sort(c,c+m); int l=0,r=m-1,ans; while(l<=r){ int mid = (l+r)/2; int tmp = c[mid]; if(check(tmp) <= t){ ans = tmp; l = mid+1; }else{ r = mid-1; } } cout << ans << endl; } return 0;}

上一篇：删除字符串中指定的字符

下一篇：nginx源码学习（二）

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注