Submission #1330918

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
//---------------------------------------------------------------------------------------------------
template<int NV, class V> struct MinCostFlow {
    struct edge { int to, capacity; V cost; int reve;
        edge(int a, int b, V c, int d) { to = a; capacity = b; cost = c; reve = d; } };
    vector<edge> E[NV];
    int prev_v[NV], prev_e[NV]; V dist[NV];
    void add_edge(int x, int y, int cap, V cost) {
        E[x].push_back(edge(y, cap, cost, (int)E[y].size()));
        E[y].push_back(edge(x, 0, -cost, (int)E[x].size() - 1)); /* rev edge */
    }
    V mincost(int from, int to, int flow) { // 流せないなら-1が返る
        V res = 0; int i, v; rep(i, 0, NV) prev_v[i] = 0; rep(i, 0, NV) prev_e[i] = 0;
        while (flow>0) {
            fill(dist, dist + NV, numeric_limits<V>::max() / 2); dist[from] = 0;
            priority_queue<pair<int, int> > Q; Q.push(make_pair(0, from));
            while (Q.size()) { int d = -Q.top().first, cur = Q.top().second; Q.pop();
                if (dist[cur] != d) continue; if (d == numeric_limits<V>::max() / 2) break;
                rep(i, 0, E[cur].size()) {
                    edge &e = E[cur][i];
                    if (e.capacity>0 && dist[e.to]>d + e.cost) {
                        dist[e.to] = d + e.cost; prev_v[e.to] = cur; prev_e[e.to] = i;
                        Q.push(make_pair(-dist[e.to], e.to)); } } }
            if (dist[to] == numeric_limits<V>::max() / 2) return -1; int lc = flow;
            for (v = to; v != from; v = prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
            flow -= lc; res += lc*dist[to];
            for (v = to; v != from; v = prev_v[v]) { edge &e = E[prev_v[v]][prev_e[v]];
                e.capacity -= lc; E[v][e.reve].capacity += lc; } } return res;}
};
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧  
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i     
　　　　／　　　＼　 　  |　|     
　　　 /　　 /￣￣￣￣/　　|  
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿  
　 　　　＼/＿＿＿＿/　（u　⊃  
---------------------------------------------------------------------------------------------------*/







int N, M;
pair<int, int> A[50], B[50];
int D[50];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) {
        string s; int x, y;
        cin >> s >> x >> y;
        A[i] = { x, y };
    }
    map<int, vector<int>> dic;
    rep(i, 0, M) {
        string s; int m, x, y;
        cin >> s >> m >> x >> y;
        B[i] = { x, y };
        D[i] = m;
        dic[m].push_back(i);
    }

    int K = min(N, M);
    int cnt = 0;

    MinCostFlow<110, int> mcf;
    int s = N + M, t = N + M + 1, tt = N + M + 2;

    for (auto ite = dic.rbegin(); ite != dic.rend(); ite++) {
        int ma = ite->first;
        auto v = ite->second;


        if (cnt + v.size() < K) {
            for (int i : v) mcf.add_edge(i + N, t, 1, 0);
            cnt += v.size();
        }
        else if (cnt < K) {
            for (int i : v) mcf.add_edge(i + N, tt, 1, 0);
            mcf.add_edge(tt, t, K - cnt, 0);
            cnt += v.size();
        }
    }

    rep(i, 0, N) mcf.add_edge(s, i, 1, 0);
    rep(i, 0, N) rep(j, 0, M) {
        int d = abs(A[i].first - B[j].first) + abs(A[i].second - B[j].second);
        if (D[j] == 0) d = 0;
        mcf.add_edge(i, j + N, 1, d);
    }

    cout << mcf.mincost(s, t, K) << endl;
}

Submission Info

Judge Result