G. Gasoline

题目连接

题目大意：有 p p p个加油站， r r r 个运油点，每个加油站都有个需求值，每个运油点都有储存的油量值。 c c c 条连边，每条边包含三个信息 ( v , u , t ) (v, u, t) (v,u,t) 表示从第 u u u 个运油点可到达第 v v v 号加油站，且需要花费时间 t t t 。现在问要满足所有加油站的需求，走的花费最长时间的路最小是多少。

解：

我们首先将边按照时间花费为键值从小到大排序，然后对存边的数组去二分，每次将下标范围在 [ 0 , m i d ] [0, mid] [0,mid] 内的边作为新图跑一遍最大流，满足条件就减小右端点，否则增大左端点，找到最后一个满足条件的 m i d mid mid ，输出其对应时间消费即可，不存在输出 − 1 -1 −1 。

证：我们这样的操作就是在求用排序后的下标范围在 [ 0 , x ] [0, x] [0,x] 边可以满足条件的最小 x x x 。那先在我们已知用 [ 0 , x ] [0,x] [0,x] 的边可以满足条件，其中最长时间边就是 x x x 边对应的时间。反证法，倘若存在有更短的最长花费的方案，那么这些方案中的边肯定存在于 [ 0 , y ] ( y < x ) [0, y](y<x) [0,y](y<x) 中，那么我们用 [ 0 , y ] [0,y] [0,y] 中的所有边肯定也满足条件（因为边越多选择越多，部分满足条件，再多选一些一定也满足），那么我们二分的终点就不会是 x x x 而是 y y y ，即不存在更短的最长花费。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e3 + 10;
const int C = 2e4 + 10;
const int INF = 2e9;

struct Edge {
    int u;
    int v;
    int w;
}edge[C];
struct eg{
    int to;
    int cap;
    int rev;
};
vector<eg> G[N];
int level[N];
int iter[N];
int p, r, c, demand;
int wp[N], wr[N];

bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}

void add(int from,int to,int cap){
	G[from].push_back({to, cap, (int)G[to].size()});
	G[to].push_back({from, 0, (int)G[from].size() - 1});
}

void bfs(int s){
	memset(level,-1,sizeof(level));
	queue<int> que;
	level[s] = 0;
	que.push(s);
	while(!que.empty()){
		int v=que.front(); que.pop();
		for(int i=0;i<G[v].size();++i){
			eg &e=G[v][i];
			if(e.cap>0 && level[e.to]<0){
				level[e.to]=level[v]+1;
				que.push(e.to);
			}
		}
	}
}

int dfs(int v,int t,int f){
	if(v==t) return f;
	for(int &i=iter[v]; i<G[v].size(); ++i){
		eg &e=G[v][i];
		if(e.cap>0 && level[v]<level[e.to]){
			int d=dfs(e.to,t,min(f,e.cap));
			if(d>0){
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
    return 0;
}

int min_cut(int s,int t){
	int flow = 0;
	for(;;){
		bfs(s);
		if(level[t] < 0) return flow;
		memset(iter,0,sizeof(iter));
		int f;
		while((f = dfs(s,t,INF))>0){
			flow += f;
		}
	}
}

bool isok(int mid) {
    for (int i = 0; i <= p + r + 1; ++i) {
        G[i].clear();
    }
    for (int i = 1; i <= r; ++i) { // 与超级源点连边
        add(0, i, wr[i]);
    }
    for (int i = r + 1; i <= r + p; ++i) { // 与超级汇点连边
        add(i, r + p + 1, wp[i - r]);
    }
    for (int i = 0; i <= mid; ++i) {
        add(edge[i].u, edge[i].v + r, wp[edge[i].v]);
        //cout << edge[i].u << ' ' << edge[i].v + r << ' ' << wp[edge[i].v] << endl;
    }
    if (min_cut(0, r + p + 1) < demand) return false;
    return true;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    scanf("%d%d%d", &p, &r, &c);
    for (int i = 1; i <= p; ++i) {
        scanf("%d", &wp[i]);
        demand += wp[i];
    }
    for (int i = 1; i <= r; ++i) {
        scanf("%d", &wr[i]);
    }
    for (int i = 0; i < c; ++i) {
        scanf("%d%d%d", &edge[i].v, &edge[i].u, &edge[i].w);
    }
    sort(edge, edge + c, cmp);
    int L = 0, R = c - 1;
    while(L <= R) {
        int mid = L + R >> 1;
        if (isok(mid)) {
            R = mid - 1;
        }
        else {
            L = mid + 1;
        }
    }
    if (R + 1 >= c) {
        printf("-1");
    }
    else {
        printf("%d", edge[R + 1].w);
    }
}