백준 1585 - 경찰

백준 1585 - 경찰

풀이

최대유량 최소비용 문제이다.
들어오는 시간을 s, 나가는 시간을 e라 할 때 $s < e$ 이면서 걸린 시간 $S(= e-s)$라 하자.
$min((T-S)^2, F)$를 간선의 cost로 정한다.

max flow의 값이 N인지 확인하고 아니라면 -1을 출력한다.
만약 N이라면 최소 비용과 최대 비용을 각각 출력해주면 된다.

코드

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For_IMPL(condition, i, a, b, increment, decrement) \
    for (int i = (a); condition; (a < b ? increment : decrement))
#define For(i, a, b) For_IMPL((a < b ? i < b : i > b), i, a, b, ++i, --i)
#define For_(i, a, b) For_IMPL((a < b ? i <= b : i >= b), i, a, b, ++i, --i)
#define ft first
#define sd second

using namespace std;
using ll = long long;
using lll = __int128_t;
using ulll = __uint128_t;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF = 987654321;
const int INF0 = numeric_limits<int>::max();
const ll LNF = 987654321987654321;
const ll LNF0 = numeric_limits<ll>::max();

template <class T> struct MinCost_MaxFlow {
    int N;
    struct Edge {
        int to, rev;
        T cap, cost;
    };
    vector<vector<Edge>> g; // adjacent list
    vector<T> dist; // min dist(cost) from source
    vector<int> pv, pe; // prev's vertex and edge number
    vector<bool> inQ; // is it in queue?

    MinCost_MaxFlow(int _N) : N(_N), g(_N), dist(_N, 0), pv(_N), pe(_N), inQ(_N, false) {}

    void clear() {
        for(int i=0; i<N; i++) g[i].clear();
    }

    void add_edge(int u, int v, T cap, T cost) {
        int u_idx = g[u].size();
        int v_idx = g[v].size();
        if(u == v) v_idx++;
        g[u].emplace_back(Edge{v, v_idx, cap, cost});
        g[v].emplace_back(Edge{u, u_idx, (T)0, -cost});
    }
    bool SPFA(int src, int sink) {
        dist = vector<T>(N, numeric_limits<T>::max());
        inQ = vector<bool>(N, false);
        queue<int> q;

        dist[src] = 0; inQ[src] = true;
        q.push(src);
        while(!q.empty()) {
            int here = q.front(); q.pop();
            inQ[here] = false;
            for(int i=0; i<g[here].size(); i++) {
                Edge edge = g[here][i];
                int there = edge.to;
                if(edge.cap>0 && dist[there] > dist[here] + edge.cost) {
                    dist[there] = dist[here] + edge.cost;
                    pv[there] = here; pe[there] = i;
                    if(!inQ[there]) inQ[there] = true, q.push(there);
                }
            }
        }

        return dist[sink] != numeric_limits<T>::max();
    }

    pair<T,T> MCMF(int src, int sink) {
        T min_cost = 0, max_flow = 0;
        while(SPFA(src, sink)) {
            T flow = numeric_limits<T>::max();
            for(int pos=sink; pos!=src; pos=pv[pos])
                flow = min(flow, g[pv[pos]][pe[pos]].cap);
            min_cost += dist[sink] * flow;
            max_flow += flow;
            for(int pos=sink; pos!=src; pos=pv[pos]) {
                int rev = g[pv[pos]][pe[pos]].rev;
                g[pv[pos]][pe[pos]].cap -= flow;
                g[pos][rev].cap += flow;
            }
        }
        return {min_cost, max_flow};
    }
};

void solve() {
    int n; cin >> n;
    vector<int> s(n+1), e(n+1);
    For_(i,1,n) cin >> s[i];
    For_(i,1,n) cin >> e[i];

    int t, f; cin >> t >> f;

    MinCost_MaxFlow<int> Min(102), Max(102);
    const int src = 0, sink = 101;
    // connect with src
    For_(i,1,n) {
        Min.add_edge(src,i,1,0);
        Max.add_edge(src,i,1,0);
    }
    // connect with sink
    For_(j,1,n) {
        Min.add_edge(50+j,sink,1,0);
        Max.add_edge(50+j,sink,1,0);
    }
    For_(i,1,n) {
        For_(j,1,n) {
            if(s[i] >= e[j]) continue;
            if(e[j] - s[i] >= t) {
                Min.add_edge(i,50+j,1,0);
                Max.add_edge(i,50+j,1,0);
            }
            else {
                int cost = min((t-(e[j]-s[i]))*(t-(e[j]-s[i])), f);
                Min.add_edge(i,50+j,1,cost);
                Max.add_edge(i,50+j,1,-cost);
            }
        }
    }
    auto resMin = Min.MCMF(src, sink);
    auto resMax = Max.MCMF(src, sink);
    if(resMin.sd != n) {
        cout << "-1\n";
        return;
    }
    cout << resMin.ft << ' ' << -resMax.ft << endl;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int tc = 1;
//    cin >> tc;
    while(tc--) {
        solve();
//        cout << solve() << endl;
    }


    return 0;
}