結果

問題 No.1324 Approximate the Matrix
ユーザー pes_magicpes_magic
提出日時 2020-12-21 22:59:33
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 90 ms / 2,000 ms
コード長 3,346 bytes
コンパイル時間 1,254 ms
コンパイル使用メモリ 93,964 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-21 13:12:39
合計ジャッジ時間 3,880 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 87 ms
6,944 KB
testcase_04 AC 85 ms
6,940 KB
testcase_05 AC 87 ms
6,940 KB
testcase_06 AC 86 ms
6,940 KB
testcase_07 AC 87 ms
6,940 KB
testcase_08 AC 11 ms
6,944 KB
testcase_09 AC 7 ms
6,944 KB
testcase_10 AC 14 ms
6,940 KB
testcase_11 AC 26 ms
6,944 KB
testcase_12 AC 6 ms
6,940 KB
testcase_13 AC 5 ms
6,940 KB
testcase_14 AC 28 ms
6,944 KB
testcase_15 AC 12 ms
6,944 KB
testcase_16 AC 3 ms
6,944 KB
testcase_17 AC 17 ms
6,940 KB
testcase_18 AC 7 ms
6,940 KB
testcase_19 AC 6 ms
6,944 KB
testcase_20 AC 5 ms
6,940 KB
testcase_21 AC 3 ms
6,944 KB
testcase_22 AC 6 ms
6,944 KB
testcase_23 AC 15 ms
6,944 KB
testcase_24 AC 34 ms
6,944 KB
testcase_25 AC 19 ms
6,940 KB
testcase_26 AC 18 ms
6,944 KB
testcase_27 AC 9 ms
6,940 KB
testcase_28 AC 2 ms
6,944 KB
testcase_29 AC 2 ms
6,944 KB
testcase_30 AC 2 ms
6,940 KB
testcase_31 AC 2 ms
6,944 KB
testcase_32 AC 2 ms
6,944 KB
testcase_33 AC 2 ms
6,940 KB
testcase_34 AC 2 ms
6,944 KB
testcase_35 AC 2 ms
6,940 KB
testcase_36 AC 2 ms
6,944 KB
testcase_37 AC 90 ms
6,940 KB
testcase_38 AC 90 ms
6,940 KB
testcase_39 AC 89 ms
6,940 KB
testcase_40 AC 89 ms
6,940 KB
testcase_41 AC 90 ms
6,940 KB
testcase_42 AC 11 ms
6,940 KB
testcase_43 AC 10 ms
6,940 KB
testcase_44 AC 10 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

template<typename CAP, typename COST>
class MinCostFlow {
public:
    explicit MinCostFlow(int N) : g(N) {}
    void addEdge(int src, int dst, CAP cap, COST cost){
        int r1 = g[src].size();
        int r2 = g[dst].size();
        g[src].emplace_back(src, dst, cap, cost, r2);
        g[dst].emplace_back(dst, src, 0, -cost, r1);
    }
    pair<COST, CAP> solve(int s, int t, CAP maxFlow){
        const int n = g.size();
        pair<COST, CAP> res = make_pair(0, 0);
        vector<COST> h(n, 0);
        while(maxFlow > 0){
            vector<COST> dist(n, INF); dist[s] = 0;
            vector<pair<int, int>> prev(n, make_pair(-1, -1));
            priority_queue<pair<COST, int>, vector<pair<COST, int>>, greater<pair<COST, int>>> qu;
            qu.emplace(0, s);
            while(!qu.empty()){
                auto e = qu.top(); qu.pop();
                if(dist[e.second] < e.first) continue;
                for(int i=0;i<g[e.second].size();i++){
                    auto& p = g[e.second][i];
                    if(p.cap > 0 && dist[p.dst] > dist[p.src] + p.cost + h[p.src] - h[p.dst]){
                        dist[p.dst] = dist[p.src] + p.cost + h[p.src] - h[p.dst];
                        prev[p.dst] = make_pair(p.src, i);
                        qu.emplace(dist[p.dst], p.dst);
                    }
                }
            }
            if(prev[t].first == -1) break;
            CAP f = maxFlow;
            for(int u=t;u!=s;u=prev[u].first) f = min(f, g[prev[u].first][prev[u].second].cap);
            for(int u=t;u!=s;u=prev[u].first){
                auto& p = g[prev[u].first][prev[u].second];
                auto& q = g[p.dst][p.rev];
                res.first += f * p.cost;
                p.cap -= f;
                q.cap += f;
            }
            res.second += f;
            for(int i=0;i<n;i++) h[i] += dist[i];
            maxFlow -= f;
        }
        return res;
    }
private:
    class Edge {
    public:
        explicit Edge(int src, int dst, CAP cap, COST cost, int rev) : src(src), dst(dst), cap(cap), cost(cost), rev(rev) {}
        const int src;
        const int dst;
        CAP cap;
        COST cost;
        const int rev;
    };
private:
    const COST INF = 1LL << 30;
    vector<vector<Edge>> g;
};

int main(){
    int N, K;
    while(cin >> N >> K){
        vector<int> A(N), B(N);
        vector P(N, vector(N, 0));
        for(auto& t : A) cin >> t;
        for(auto& t : B) cin >> t;
        int base = 0;
        for(auto& v : P){
            for(auto& t : v){
                cin >> t;
                base += t*t;
            }
        }
        MinCostFlow<int, int> mcf(2*N+2);
        for(int i=0;i<N;i++) if(A[i] > 0) mcf.addEdge(0, i+1, A[i], 0);
        for(int i=0;i<N;i++) if(B[i] > 0) mcf.addEdge(N+1+i, 2*N+1, B[i], 0);
        const int THR = 40000;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                for(int k=0;k<A[i];k++){
                    int c1 = P[i][j] - k;
                    int c2 = P[i][j] - (k+1);
                    int c = c2*c2 - c1*c1 + THR;
                    mcf.addEdge(i+1, N+j+1, 1, c);
                }
            }
        }
        base += mcf.solve(0, 2*N+1, K).first - K*THR;
        cout << base << endl;
    }
}
0