BOJ)1745 숨기

문제: icpc.me/1745

F개의 방이 있을 때 각방마다 학생들이 숨을 수 있는 수와 현재 몇명의 학생들이 있는지 수가 주어진다. 이 때 방 A에서 B로 이동할 때 걸리는 시간이 주어질 때 모든 학생이 숨을 수 있는 최소 시간을 구하는 문제이다.

우리는 소스 -> I번 방 -> I번 방에서 ->J번 방으로 연결 된 정점 -> J번 방 ->싱크로 모델링을 하여 모든 학생들이 숨을 수 있는지 여부를 알 수 있다.

이때 capacity를 소스 -> I번 방은 현재 i번방에 있는 학생 수 / J번 방 -> 싱크는 j번 방에 숨을 수 있는 학생 수 나머지는 INF를 주면 된다.

이렇게 하여서 흘린 maximum flow가 현재 있는 학생들의 수의 총합과 같다면 현재 모델링에서 학생들이 전부 숨을 수 있는것이다.

이때 우리는 최소 시간을 구해야 하므로 플로이드 워셜을 통하여 각 방마다의 최소 거리를 구해준 뒤 

파라메트릭 서치를 통하여 mid보다 작은 모든 정점들을 I번 방 -> I번 방에서 ->J번 방으로 연결 된 정점 -> J번 방 으로 모델링 해줌으로 서 여부를 파악한다.

정점이 약 f*f+2*f 개 가량이므로 디닉으로 maximum flow를 구하지 않는다면 TLE를 받을 수 있다.

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
#define INF 987654321
typedef long long ll;
using namespace std;
struct Dinic {
    ll n;
    struct Edge {
        ll v, cap, rev;
        Edge(ll v, ll cap, ll rev) :v(v), cap(cap), rev(rev) {}
    };
    vector<vector<Edge>> vt;
    void addEdge(ll s, ll e, ll c) {
        vt[s].emplace_back(e, c, vt[e].size());
        vt[e].emplace_back(s, 0, vt[s].size() - 1);
    }
    vector<ll> level, work;
    Dinic(ll n) :n(n) {
        vt.resize(n + 1);
        level.assign(n + 1, -1);
        work.assign(n + 1, 0);
    }
    bool bfs(ll src, ll sink) {
        level.assign(n + 1, -1);
        queue<ll> qu;
        level[src] = 0;
        qu.push(src);
        while (qu.size()) {
            ll here = qu.front();
            qu.pop();
            for (auto i : vt[here]) {
                if (i.cap > 0 && level[i.v] == -1) {
                    level[i.v] = level[here] + 1;
                    qu.push(i.v);
                }
            }
        }
        return level[sink] != -1;
    }
    ll dfs(ll sink, ll here, ll crtcap) {
        if (sink == here)return crtcap;
        for (ll &i = work[here]; i < vt[here].size(); i++) {
            ll cap = vt[here][i].cap;
            ll there = vt[here][i].v;
            if (level[here] + 1 == level[there] && cap>0) {
                ll c = dfs(sink, there, min(crtcap, cap));
                if (c) {
                    vt[here][i].cap -= c;
                    vt[there][vt[here][i].rev].cap += c;
                    return c;
                }
            }
        }
        return 0;
    }
    ll solve(ll src, ll sink) {
        ll ret = 0;
        while (bfs(src, sink)) {
            work.assign(n + 1, 0);
            while (1) {
                ll flow = dfs(sink, src, INF);
                if (!flow)break;
                ret += flow;
            }
        }
        return ret;
    }
};
ll f, p, a[202][202], x, y, z, b[202], c[202], n;
int main() {
    memset(a, 0x3f, sizeof(a));
    scanf("%lld%lld", &f, &p);
    for (ll i = 1; i <= f; i++) {
        scanf("%lld%lld", &b[i], &c[i]);
        n += b[i];
    }
    for (ll i = 0; i < p; i++) {
        scanf("%lld%lld%lld", &x, &y, &z);
        a[x][y] = min(z, a[x][y]);
        a[y][x] = min(z, a[y][x]);
    }
    for (ll i = 1; i <= f; i++) {
        for (ll j = 1; j <= f; j++) {
            for (ll k = 1; k <= f; k++) {
                if (j == k)a[j][k] = 0;
                if (a[j][i] + a[i][k] < a[j][k])
                    a[j][k] = a[j][i] + a[i][k];
            }
        }
    }
    ll lo = 0, hi = 1000000000010;
    while (lo < hi) {
        Dinic d(f*f + 2 * f + 3);
        ll mid = (lo + hi) >> 1;
        for (ll i = 1; i <= f; i++) {
            for (ll j = 1; j <= f; j++) {
                if (a[i][j] <= mid) {
                    d.addEdge(i, i*f + j, INF);
                    d.addEdge(i*f + j, f*f + f + j, INF);
                }
            }
        }
        for (ll i = 1; i <= f; i++) {
            d.addEdge(f*f + 2 * f + 1, i, b[i]);
            d.addEdge(f*f + f + i, f*f + 2 * f + 2, c[i]);
        }
        ll r = d.solve(f*f + 2 * f + 1, f*f + 2 * f + 2);
        if (r == n)
            hi = mid;
        else
            lo = mid + 1;
    }
    if (lo > 1000000000001)
        printf("-1");
    else
        printf("%lld\n", lo);
    return 0;
}