結果

問題 No.1479 Matrix Eraser
ユーザー 竹内俊暁竹内俊暁
提出日時 2022-11-11 00:59:42
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 838 ms / 3,000 ms
コード長 5,818 bytes
コンパイル時間 1,995 ms
コンパイル使用メモリ 118,612 KB
実行使用メモリ 96,684 KB
最終ジャッジ日時 2023-10-10 21:53:09
合計ジャッジ時間 17,052 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,352 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 1 ms
4,352 KB
testcase_05 AC 1 ms
4,352 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 45 ms
14,148 KB
testcase_08 AC 80 ms
22,136 KB
testcase_09 AC 189 ms
43,664 KB
testcase_10 AC 371 ms
79,608 KB
testcase_11 AC 221 ms
50,520 KB
testcase_12 AC 57 ms
16,764 KB
testcase_13 AC 82 ms
21,940 KB
testcase_14 AC 60 ms
17,776 KB
testcase_15 AC 13 ms
6,240 KB
testcase_16 AC 69 ms
19,408 KB
testcase_17 AC 456 ms
95,344 KB
testcase_18 AC 451 ms
95,216 KB
testcase_19 AC 452 ms
95,220 KB
testcase_20 AC 452 ms
96,184 KB
testcase_21 AC 461 ms
95,468 KB
testcase_22 AC 450 ms
96,284 KB
testcase_23 AC 459 ms
95,940 KB
testcase_24 AC 453 ms
96,300 KB
testcase_25 AC 464 ms
96,684 KB
testcase_26 AC 508 ms
95,820 KB
testcase_27 AC 751 ms
42,948 KB
testcase_28 AC 693 ms
43,460 KB
testcase_29 AC 787 ms
43,456 KB
testcase_30 AC 838 ms
43,008 KB
testcase_31 AC 769 ms
43,144 KB
testcase_32 AC 101 ms
29,428 KB
testcase_33 AC 100 ms
29,412 KB
testcase_34 AC 95 ms
29,388 KB
testcase_35 AC 103 ms
29,104 KB
testcase_36 AC 103 ms
29,096 KB
testcase_37 AC 43 ms
6,724 KB
testcase_38 AC 389 ms
96,120 KB
testcase_39 AC 377 ms
95,368 KB
testcase_40 AC 2 ms
4,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include <iomanip>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<bit>
#include<bitset>
#include<map>
#include<cmath>
#include <cstdint>
#include <algorithm>
#define rep(i,l,r) for(ll i=l;i<=r;i++)
static const int WH = 0;
static const int GR = 1;
static const int BL = 2;
using namespace std;
using ll = long long;
using ull = unsigned long long;
static const ll ll_INF = 1e18;
static const ll MOD =  998244353;
void chmin(ll &a, ll b){ a = min(a,b); }

struct edge {
    int from;
    int to;
    int amount;
    int init_amount;
    edge *complement;

    edge(int arg_from, int arg_to, int arg_amount) {
        from = arg_from;
        to = arg_to;
        amount = arg_amount;
        init_amount = arg_amount;
    }

    void set_value(int arg_from, int arg_to, int arg_amount, edge *arg_comp) {
        from = arg_from;
        to = arg_to;
        amount = arg_amount;
        complement = arg_comp;
    }
};

struct maxflow {
    int Node_num;
    vector<vector<edge *>> edges;
    vector<edge *> edge_list;

    maxflow(int N) {
        Node_num = N;
        edges.resize(N);
    }

    void add_edge(int from, int to, int cost) {
        edge *new_edge = new edge(from, to, cost);
        edge *new_complement_edge = new edge(to, from, 0);
        new_edge->complement = new_complement_edge;
        new_complement_edge->complement = new_edge;

        edges[from].push_back(new_edge);
        edges[to].push_back(new_complement_edge);
        edge_list.push_back(new_edge);
    }

    void sub_add_edge(edge *new_edge, vector<vector<edge *>> &vec){
        vec[new_edge->from].push_back(new_edge);
        vec[new_edge->to].push_back(new_edge->complement);
    }

    void bfs(int start_node, vector<int> &level) {
        queue<int> q;
        q.push(start_node);
        level[start_node] = 0;
        while(q.size() > 0) {
            int now_v = q.front();
            q.pop();
            for(int i = 0; i < edges[now_v].size(); i++) {
                int next_v = edges[now_v][i]->to;
                if((level[next_v] == -1) && (edges[now_v][i]->amount > 0)) {
                    level[next_v] = level[now_v] + 1;
                    q.push(next_v);
                }
            }
        }
    }

    int dfs(int u, int end_node, int f, vector<int> &level, vector<int> &iter) {
        //cout << u << " " << end_node << " " << (u == end_node) <<  endl;
        if(u == end_node)
            return f;
        while(iter[u] < edges[u].size()){
            if(level[edges[u][iter[u]]->to] == -1){
                iter[u]++;
                continue;
            }
            if(level[edges[u][iter[u]]->to] <= level[u]){
                iter[u]++;
                continue;
            }

            if(edges[u][iter[u]]->amount <= 0){
                iter[u]++;
                continue;
            }

            int final_flow = dfs(edges[u][iter[u]]->to, end_node,
                                 min(edges[u][iter[u]]->amount, f), level, iter);
            
            if(final_flow > 0){
                edges[u][iter[u]]->amount -= final_flow;
                edges[u][iter[u]]->complement->amount += final_flow;
                return final_flow;
            } else iter[u]++;
            
        }
        
        return 0;
    }

    int find_maxflow(int start_node, int end_node) {
        int ret_flow = 0;
        while(1) {
            vector<int> level;
            level.resize(Node_num, -1);
            bfs(start_node, level);
            if(level[end_node] == -1)
                break;

            vector<int> iter(Node_num,0);

            while(1) {
                int oneflow = dfs(start_node, end_node, 1e8, level,iter);
                //cout << oneflow << endl;
                if(oneflow <= 0)
                    break;
                ret_flow += oneflow;
            }
        }
        return ret_flow;
    }
};




int H,W;
vector<vector<int>> A;
vector<vector<int>> compH;
vector<vector<int>> compW;

void init(){
    cin >> H >> W;
    A.resize(H);
    compH.resize(H);
    compW.resize(H);
    rep(i,0,H-1){
        rep(j,0,W-1){
            int a; cin >> a;
            A[i].push_back(a);
            compH[i].push_back(-1);
            compW[i].push_back(-1);
        }
    }
}

void find_label_H(int &label){
    for(int i = 0; i < H; i++){
        map<int,int> mp;
        for(int j = 0; j < W; j++){
            if(mp[A[i][j]] == 0){
                label++;
                mp[A[i][j]] = label;         
            } 
            compH[i][j] =  mp[A[i][j]];
        }
    }
}

void find_label_W(int &label){
    for(int j = 0; j < W; j++){
        map<int,int> mp;
        for(int i = 0; i < H; i++){
            if(mp[A[i][j]] == 0){
                label++;
                mp[A[i][j]] = label;         
            } 
            compW[i][j] =  mp[A[i][j]];
        }
    }
}



int main(){
    init();
    int label = 0;
    find_label_H(label);
    int Hlabel = label;
    find_label_W(label);
    int Wlabel = label;
    maxflow mf(label + 2);
    /*
    cout << endl;
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cout << compH[i][j] << " ";
        }
        cout << endl;
    }

    cout << endl;
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cout << compW[i][j] << " ";
        }
        cout << endl;
    }
    */


    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            if(A[i][j] == 0) continue;
            mf.add_edge(compH[i][j], compW[i][j],1);
        }
    }
    for(int i = 1; i <= Hlabel; i++){
        mf.add_edge(0,i,1);
    }
    for(int i = Hlabel + 1; i <= Wlabel; i++){
        mf.add_edge(i,label + 1,1);
    }
    cout << mf.find_maxflow(0,label + 1) << endl;
    
    return 0;
}
0