結果

問題 No.1324 Approximate the Matrix
コンテスト
ユーザー mtsd
提出日時 2020-12-21 23:45:20
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,399 bytes
コンパイル時間 1,753 ms
コンパイル使用メモリ 139,600 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-21 13:23:00
合計ジャッジ時間 3,331 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin(T &a, T b){
    if(a>b){
        a = b;
        return true;
    }
    return false;
}
template<typename T> class Dinic {
private:
    int V;
    vector<int> level,iter;
    void bfs(int s) {
        fill(level.begin(),level.end(),-1);
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while(!que.empty()){
            int v = que.front();
            que.pop();
            for(auto& e : G[v]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    T dfs(int v,int t,T f) {
        if(v==t){
            return f;
        }
        for(int& i = iter[v]; i < (int)G[v].size(); i++){
            edge& e = G[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                T d = dfs(e.to,t,min(f,e.cap));
                if(d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
 
public:
    struct edge{
        int to;
        T cap;
        int rev;
    };
    vector<vector<edge> > G;
 
    Dinic(int node_size) : V(node_size), level(V), iter(V), G(V){}
    //辺を張る
    void add_edge(int from,int to,T cap) {
        G[from].push_back((edge){to,cap,(int)G[to].size()});
        G[to].push_back((edge){from,(T)0,(int)G[from].size()-1});
    }
    //最大流を計算
    T solve(int s,int t) {
        T flow = 0;
        for(;;){
            bfs(s);
            if(level[t] < 0) return flow;
            fill(iter.begin(),iter.end(),0);
            T f;
            while((f=dfs(s,t,numeric_limits<T>::max())) > 0){
                flow += f;
            }
        }
    }
};
int main(){
    int n,k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<int> b(n);
    rep(i,n) cin >> b[i];
    vector<vector<int> > p(n,vector<int>(n));
    priority_queue<pair<int,pair<int,int> > > pq;
    rep(i,n){
        rep(j,n){
            cin >> p[i][j];
            pq.push(MP(p[i][j],MP(i,j)));
        }
    }
    vector<vector<int> > res(n,vector<int>(n));
    while(!pq.empty()){
        auto x = pq.top();
        pq.pop();
        vector<pair<int,int> > zz;
        int iii = x.second.first;
        int jjj = x.second.second;
        if(a[iii]>0&&b[jjj]>0){
            zz.push_back(MP(iii,jjj));
            while(!pq.empty()){
                auto xx = pq.top();
                int ii = xx.second.first;
                int jj = xx.second.second;
                if(xx.first == x.first){
                    pq.pop();
                    if(a[ii]>0&&b[jj]>0){
                        zz.push_back(MP(ii,jj));
                    }
                }else{
                    break;
                }
            }
            Dinic<int> dc(2*n+2);
            int S = 2*n;
            int T = 2*n+1;
            rep(i,n){
                if(a[i]!=0){
                    dc.add_edge(S,i,a[i]);
                }
                if(b[i]!=0){
                    dc.add_edge(i+n,T,b[i]);
                }
            }
            // cerr << "test" << endl;
            for(auto xx:zz){
                // cerr << xx.first << " " << xx.second << endl;
                dc.add_edge(xx.first,xx.second + n,1);
            }
            dc.solve(S,T);
            auto &g  = dc.G;
            rep(i,n){
                for(auto xx:g[i]){
                    // cerr << i << " " <<xx.to << " " << xx.cap << endl;
                    if(xx.cap==0&&xx.to < 2*n){
                        int ii = i;
                        int jj = xx.to-n;
                        // cerr << "ok:" << ii << " " << jj << endl;
                        res[ii][jj]++;
                        a[ii]--;
                        b[jj]--;
                        pq.push(MP(x.first-1,MP(ii,jj)));
                    }
                }
            } 
        }
        // cerr << "Test" << endl;
        // rep(i,n)cerr << a[i] << " ";
        // cerr << endl;
        // rep(i,n)cerr << b[i] << " ";
        // cerr << endl;
    }
    ll ans  =0;
    // rep(i,n){
    //     rep(j,n){
    //         cerr << res[i][j] << " ";
    //     }
    //     cerr << endl;
    // }
    rep(i,n){
        rep(j,n){
            ans += (res[i][j]-p[i][j])*(res[i][j]-p[i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}
0