P2402 奶牛隐藏 二分+网络流

floyd搞出两点间最短距离 二分判答案

// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1050;
const int MAXM = 50050;
const ll INF = 1LL << 50;
ll f[MAXM << 1];
int Head[MAXN], cur[MAXN], lev[MAXN], to[MAXM << 1], nxt[MAXM << 1], ed = 1, S, T;
inline void read(ll &v)
{
    v = 0;
    char c = 0;
    ll p = 1;
    while (c < '0' || c > '9') {
        if (c == '-') {
            p = -1;
        }
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        v = (v << 3) + (v << 1) + c - '0';
        c = getchar();
    }
    v *= p;
}
inline void addedge(int u, int v, ll cap)
{
    to[++ed] = v;
    nxt[ed] = Head[u];
    Head[u] = ed;
    f[ed] = cap;
    to[++ed] = u;
    nxt[ed] = Head[v];
    Head[v] = ed;
    f[ed] = 0;
    return;
}
inline bool BFS()
{
    int u;
    memset(lev, -1, sizeof(lev));
    queue<int>q;
    lev[S] = 0;
    q.push(S);
    while (q.size()) {
        u = q.front();
        q.pop();
        for (int i = Head[u]; i; i = nxt[i])
            if (f[i] && lev[to[i]] == -1) {
                lev[to[i]] = lev[u] + 1;
                q.push(to[i]);
                /*
                if (to[i] == T)
                {
                        return 1;
                }
                magic one way optimize
                */
            }
    }
    memcpy(cur, Head, sizeof Head);
    return lev[T] != -1;
}
inline ll DFS(int u, ll maxf)
{
    if (u == T || !maxf) {
        return maxf;
    }
    ll cnt = 0, tem;
    for (int &i = cur[u]; i; i = nxt[i])
        if (f[i] && lev[to[i]] == lev[u] + 1) {
            tem = DFS(to[i], min(maxf, f[i]));
            maxf -= tem;
            f[i] -= tem;
            f[i ^ 1] += tem;
            cnt += tem;
            if (!maxf) {
                break;
            }
        }
    if (!cnt) {
        lev[u] = -1;
    }
    return cnt;
}
ll Dinic()
{
    ll ans = 0;
    while (BFS()) {
        ans += DFS(S, 1LL << 50);
    }
    return ans;
}
void init(int SS, int TT)
{
    memset(Head, 0, sizeof(Head));
    ed = 1;
    S = SS;
    T = TT;
    return;
}
ll n, m;
ll u, v , c;
ll s[MAXN], p[MAXN];
ll dis[MAXN][MAXN];
ll sum = 0;
bool check(ll x)
{
    memset(Head, 0, sizeof(Head));
    ed = 1;
    S = 0, T = 2 * n + 1;
    for (int i = 1; i <= n; i++) {
        addedge(S, i, s[i]);
        addedge(i + n, T, p[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (i == j) {
                addedge(i, i + n, INF);
            } else if (dis[i][j] <= x) {
                addedge(i, j + n, INF), addedge(j, i + n, INF);
            }
        }
    }
    if (Dinic() == sum) {
        return true;
    }
    return false;
}
int main()
{
    ll x;
    read(n), read(m);
    for (int i = 1; i <= n; i++) {
        read(x), s[i] = x;
        read(x), p[i] = x;
        sum += s[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                dis[i][j] = 0;
            } else {
                dis[i][j] = 1LL << 50;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        read(u), read(v), read(c);
        dis[u][v] = dis[v][u] = min(dis[u][v], c);
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dis[i][j] > dis[i][k] + dis[k][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    ll l = INF, r = -INF, mid;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j) {
                if (dis[i][j] >= INF) {
                    continue;
                }
                r = max(dis[i][j], r);
                l = min(l, dis[i][j]);
            }
        }
    }
    r++, l--;
    bool flag = false;
    while (l < r - 1) {
        mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
            flag = true;
        } else {
            l = mid;
        }
    }
    if (flag) {
        cout << r << endl;
    } else {
        cout << -1 << endl;
    }
    return 0;
}