Gym - 101908G 二分答案+最大流
After the end of the truck drivers' strike, you and the rest of Nlogônia logistics specialists now have the task of planning the refueling of the gas stations in the city. For this, we collected information on stocks of R refineries and about the demands of P
gas stations. In addition, there are contractual restrictions that some refineries cannot supply some gas stations; When a refinery can provide a station, the shorter route to transport fuel from one place to another is known.
The experts' task is to minimize the time all stations are supplied, satisfying their demands. The refineries have a sufficiently large amount of trucks, so that you can assume that each truck will need to make only one trip from a refinery to a gas station. The capacity of each truck is greater than the demand of any gas station, but it may be necessary to use more than one refinery.
Input
The first line of the input contains three integers P,R,C
, respectively the number of gas stations, the number of refineries and the number of pairs of refineries and gas stations whose time will be given (1≤P,R≤1000; 1≤C≤20000). The second line contains P integers Di (1≤Di≤104), representing the demands in liters of gasoline of the gas stations i=1,2,…,P, in that order. The third line contains R integers Ei (1≤Ei≤104), representing stocks, in liters of gasoline, of refineries i=1,2,…,R, in that order. Finally, the latest C lines describe course times, in minutes, between stations and refineries. Each of these rows contains three integers, I,J,T (1≤I≤P; 1≤J≤R; 1≤T≤106), where I is the ID of a post, J is the ID of a refinery and T is the time in the course of a refinery truck J to I. No pair (J,I)
repeats. Not all pairs are informed; If a pair is not informed, contractual restrictions prevents the refinery from supplying the station.
Output
Print an integer that indicates the minimum time in minutes for all stations to be completely filled up. If this is not possible, print −1.
Examples
3 2 5
20 10 10
30 20
1 1 2
2 1 1
2 2 3
3 1 4
3 2 5
4
3 2 5
20 10 10
25 30
1 1 3
2 1 1
2 2 4
3 1 2
3 2 5
5
4 3 9
10 10 10 20
10 15 30
1 1 1
1 2 1
2 1 3
2 2 2
3 1 10
3 2 10
4 1 1
4 2 2
4 3 30
-1
1 2 2
40
30 10
1 1 100
1 2 200
200
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
//#include<cctype>
//#pragma GCC optimize(2)
using namespace std;
#define maxn 300005
#define inf 0x7fffffff
//#define INF 1e18
#define rdint(x) scanf("%d",&x)
#define rdllt(x) scanf("%lld",&x)
#define rdult(x) scanf("%lu",&x)
#define rdlf(x) scanf("%lf",&x)
#define rdstr(x) scanf("%s",x)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int U;
#define ms(x) memset((x),0,sizeof(x))
const long long int mod = 1e9;
#define Mod 1000000000
#define sq(x) (x)*(x)
#define eps 1e-5
typedef pair<int, int> pii;
#define pi acos(-1.0)
//const int N = 1005;
#define REP(i,n) for(int i=0;i<(n);i++)
typedef pair<int, int> pii; inline int rd() {
int x = 0;
char c = getchar();
bool f = false;
while (!isdigit(c)) {
if (c == '-') f = true;
c = getchar();
}
while (isdigit(c)) {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return f ? -x : x;
} ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a%b);
}
int sqr(int x) { return x * x; } /*ll ans;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1; y = 0; return a;
}
ans = exgcd(b, a%b, x, y);
ll t = x; x = y; y = t - a / b * y;
return ans;
}
*/ int n, m;
int st, ed;
struct node {
int u, v, nxt, w;
}edge[maxn << 1]; int head[maxn], cnt; void addedge(int u, int v, int w) {
edge[cnt].u = u; edge[cnt].v = v; edge[cnt].nxt = head[u];
edge[cnt].w = w; head[u] = cnt++;
} int rk[maxn]; int bfs() {
queue<int>q;
ms(rk);
rk[st] = 1;
q.push(st);
while (!q.empty()) {
int tmp = q.front(); q.pop();
for (int i = head[tmp]; i != -1; i = edge[i].nxt) {
int to = edge[i].v;
if (rk[to] || edge[i].w <= 0)continue;
rk[to] = rk[tmp] + 1; q.push(to);
}
}
return rk[ed];
} int dfs(int u, int flow) {
if (u == ed)return flow;
int add = 0;
for (int i = head[u]; i != -1 && add < flow; i = edge[i].nxt) {
int v = edge[i].v;
if (rk[v] != rk[u] + 1 || !edge[i].w)continue;
int tmpadd = dfs(v, min(edge[i].w, flow - add));
if (!tmpadd) { rk[v] = -1; continue; }
edge[i].w -= tmpadd; edge[i ^ 1].w += tmpadd;
add += tmpadd;
}
return add;
} int ans;
void dinic() {
while (bfs())ans += dfs(st, inf);
} int P, R, C;
int D[maxn], E[maxn], T;
int sum;
struct nd {
int u, v, w;
}e[maxn]; bool chk(int x) {
ms(edge); memset(head, -1, sizeof(head)); cnt = 0;
ms(rk);
ans = 0;
st = 0; ed = P + R + 2;
for (int i = 1; i <= R; i++)addedge(st, i, E[i]), addedge(i, st, 0);
for (int i = 1; i <= P; i++)addedge(i + R, ed, D[i]), addedge(ed, i + R, 0);
for (int i = 1; i <= C; i++) {
if (x >= e[i].w) {
addedge(e[i].v, e[i].u + R, inf); addedge(e[i].u + R, e[i].v, 0);
}
}
dinic();
if (ans == sum)return true;
return false;
}
int main()
{
// ios::sync_with_stdio(0);
memset(head, -1, sizeof(head)); P = rd(); R = rd(); C = rd();
for (int i = 1; i <= P; i++) {
D[i] = rd(); sum += D[i];// gas stations
}
for (int i = 1; i <= R; i++)E[i] = rd();
for (int i = 1; i <= C; i++)e[i].u = rd(), e[i].v = rd(), e[i].w = rd();
bool fg = 0;
int l = 0, r = 1e7 + 1;
int as = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (chk(mid)) {
r = mid - 1; as = mid; fg = 1;
}
else l = mid + 1;
}
if (!fg)cout << -1 << endl;
else cout << as << endl;
return 0;
}
最新文章
- 谷歌浏览器如何查看或获取Cookie字符串
- CSS list-style属性控制ul标签样式
- mongoose学习文档
- log4j的配置信息
- JS数组2(冒泡排列、数组里面查找数据)
- Factory Method模式
- jquery回调函数callback的使用
- Android SurfaceView实战 打造抽奖转盘
- HDU 1874 畅通工程续(模板题——Floyd算法)
- python3下GUI界面设计之控件精确定位
- FIN_WAIT_2状态解释
- XBee 802.15.4/Digimesh FAQs:如何为2.4G模块选择合适的信道
- django学习第一天
- Android 爬坑之路
- 用v-if 来给不同筛选出来的todo添加不同的按钮
- #define SIG_DFL ((void(*)(int))0)
- HDU 3374 String Problem(KMP+最大(最小)表示)
- ceph部署过程中的错误
- php中的namespace 命名空间
- CEntOS6.5从启动界面直接进入命令行界面
热门文章
- Spring Cloud Feign 1(声明式服务调用Feign 简介)
- Leetcode:Longest Substring Without Repeating Characters分析和实现
- mfs测试
- dataTable写入数据库(大数据写入)
- 【项目运行异常】BeanFactory not initialized or already closed - call &#39;refresh&#39; before accessing beans via the ApplicationContext
- Jmeter接口测试-获取所有任务API
- 【2008nmj】Logistic回归二元分类感知器算法.docx
- poj2513 Fence Repair(小根堆)
- Ext JS v2.3.0 Ext.grid.ColumnModel renderer Record 获取列值
- 学习React中遇到的问题