题解 | #Tachibana Kanade And Dream City#

原题解链接：https://ac.nowcoder.com/discuss/173818

简单的网络流题。

抛开要求时间的限制，我们直接考虑如何判断这些废水是否可以被处理。我们把每户人家看做一个点，发现限制主要是在点而不是在边，我们就可以很自然地将每个点$vv$ 拆成两个点$v_{1}v\_1$ ​ 和$v_{2}v\_2$ ，建立源点$SS$ 和汇点$TT$，对于每一个$vv$，我们建立源点到 $v_{1}v\_1$ ​ 的弧，容量为该点一开始拥有废水的数量$v_{i}v\_i$ ，$v_{2}v\_2$ ​ 连向 $TT$一条容量为废水处理数量$w_{i}w\_i$ ​ 的弧。对于原图的每一条边 $(a,b)(a,b)$，连接 $a_{1}a\_1$ ​ 和 $b_{2}b\_2$ ​ 一条容量为无限大的弧。 该网络的最大流等价于最大能处理的废水数量。

现在我们要求能处理前提下的最短时间，发现是让所有安排方案中花费时间最大的方案花费时间最小，我们发现「最大的时间花费最小」是一个经典的带有单调性的问题。首先跑$\text{Floyd}\backslash text\{Floyd\}$确定任意两点间的最短路径，二分最大值$LL$ 后直接对于每对最短距离 $\le L\backslash leq\; L$的点对直接建立上述的边就可以了。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <bits/stdc++.h>
#include <set>

#define Re register
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define SFOR(i,a,b,c) for(Re int i = a;i <= b;i+=c)
#define SROF(i,a,b,c) for(Re int i = a;i >= b;i-=c)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------\n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 2000 + 5;
const int MAXM = 500000 + 5;
#define int LL
struct Node{
    struct Edge *first,*cur;
    int level;
}node[MAXN];

struct Edge{
    Node *s,*t;
    Edge *next,*rev;
    int cap,flow;
}pool[MAXM<<1],*frog = pool;

inline void init(){
    CLR(pool,0);CLR(node,0);
    frog = pool;
}

Edge *New(Node *s,Node *t,int cap){
    Edge *ret = ++frog;
    *ret = (Edge){s,t,s->first,NULL,cap,0};
    return ret;
}

inline void add(int u,int v,int cap){
    // printf("%lld %lld %lld\n",u,v,cap);
    node[u].first = New(&node[u],&node[v],cap);
    node[v].first = New(&node[v],&node[u],0);
    node[u].first->rev = node[v].first;
    node[v].first->rev = node[u].first;
}

int N,S,T;

bool bfs(Node *s,Node *t){
    FOR(i,0,N){
        node[i].cur = node[i].first;
        node[i].level = 0;
    }
    std::queue<Node *> q;
    q.push(s);s->level = 1;
    while(!q.empty()){
        Node *v = q.front();q.pop();
        for(Edge *e = v->first;e;e = e->next){
            if(e->flow < e->cap && !e->t->level){
                e->t->level = v->level + 1;
                if(e->t == t) return true;
                q.push(e->t);
            }
        }
    }
    return false;
}

int dfs(Node *v,Node *t,int limit=LLONG_MAX){
    if(v == t) return limit;
    int flow;
    for(Edge *&e = v->cur;e;e = e->next){
        if(e->flow < e->cap && e->t->level == v->level + 1){
            if((flow = dfs(e->t,t,std::min(limit,e->cap - e->flow)))){
                e->flow += flow;
                e->rev->flow -= flow;
                return flow;
            }
        }
    }
    return 0;
}

inline int dinic(){
    int flow,ans = 0;
    while(bfs(&node[S],&node[T])){
        while((flow = dfs(&node[S],&node[T]))){
            ans += flow;
        }
    }
    return ans;
}

LL f[MAXN][MAXN];
int a[MAXN],b[MAXN];
int n,m,sum;

inline void Floyd(){
    FOR(k,1,n){
        FOR(i,1,n){
            FOR(j,1,n){
                f[i][j] = std::min(f[i][j],f[i][k] + f[k][j]);
            }
        }
    }
}

struct Data{
    int u,v,w;
}d[MAXM];

inline bool check(LL k){
    init();
    S = 0,T = 2*n+1;N = T;
    FOR(i,1,n) add(S,i,a[i]);
    FOR(i,1,n) add(i+n,T,b[i]);
    //FOR(i,1,n) add(i,i+n,b[i]);
    FOR(i,1,n) FOR(j,1,n){
        //if(i == j) continue;
        if(f[i][j] <= k) add(i,j+n,sum);//,printf("Link: %d %d\n",i,j);
    }
    int ans = dinic();//DEBUG(ans);
    // BR;
    return (sum <= ans);
}

int line[MAXM],top = 0;
const int INF = 1000000000ll*MAXN;
signed main(){
    scanf("%lld%lld",&n,&m);
    LL L = 0,R = 0;
    FOR(i,1,n) FOR(j,1,n) f[i][j] = INF;
    //DEBUG(INF);
    FOR(i,1,n) f[i][i] = 0;
    FOR(i,1,n) scanf("%lld%lld",a+i,b+i),assert(a[i]<=1000),assert(b[i]<=1000);
    FOR(i,1,n) sum += a[i];
    // FOR(i,1,n) FOR(j,1,n) printf("%lld%c",f[i][j],(j == n) ? '\n' : ' ');
    FOR(i,1,m){
        int u,v;LL w;
        scanf("%lld%lld%lld",&u,&v,&w);
        d[i] = (Data){u,v,w};
        f[u][v] = f[v][u] = std::min(f[u][v],w);
        R += w;
    }
    Floyd();
    std::set<int> S;
    //FOR(i,1,n) FOR(j,1,n) printf("%lld%c",f[i][j],(j == n) ? '\n' : ' ');
    FOR(i,1,n) FOR(j,1,n) if(f[i][j] != INF) S.insert(f[i][j]);
    for(std::set<int>::iterator it = S.begin();it != S.end();it++){
        line[++top] = *it;
    }
    LL ans = -1;
    L = 1,R = top;
    //DEBUG(check(70));
    while(L <= R){
        LL mid = (L+R)>>1;
        if(check(line[mid])) R = mid - 1,ans = mid;
        else L = mid + 1;
    }
    printf("%lld\n",ans == -1 ? ans : line[ans]);
    return 0;
}