結果

問題 No.1479 Matrix Eraser
ユーザー 竹内俊暁竹内俊暁
提出日時 2022-11-11 00:59:42
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 813 ms / 3,000 ms
コード長 5,818 bytes
コンパイル時間 1,478 ms
コンパイル使用メモリ 119,112 KB
実行使用メモリ 96,736 KB
最終ジャッジ日時 2024-09-13 01:26:25
合計ジャッジ時間 15,429 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 51 ms
14,316 KB
testcase_08 AC 88 ms
22,400 KB
testcase_09 AC 200 ms
44,412 KB
testcase_10 AC 379 ms
79,680 KB
testcase_11 AC 234 ms
50,768 KB
testcase_12 AC 63 ms
17,092 KB
testcase_13 AC 94 ms
22,040 KB
testcase_14 AC 67 ms
17,856 KB
testcase_15 AC 14 ms
6,944 KB
testcase_16 AC 77 ms
19,636 KB
testcase_17 AC 467 ms
95,356 KB
testcase_18 AC 471 ms
96,736 KB
testcase_19 AC 474 ms
96,652 KB
testcase_20 AC 472 ms
95,708 KB
testcase_21 AC 469 ms
96,280 KB
testcase_22 AC 474 ms
95,220 KB
testcase_23 AC 475 ms
95,832 KB
testcase_24 AC 470 ms
95,644 KB
testcase_25 AC 478 ms
95,732 KB
testcase_26 AC 528 ms
95,616 KB
testcase_27 AC 786 ms
42,816 KB
testcase_28 AC 730 ms
43,416 KB
testcase_29 AC 795 ms
43,024 KB
testcase_30 AC 813 ms
43,440 KB
testcase_31 AC 744 ms
43,228 KB
testcase_32 AC 105 ms
29,428 KB
testcase_33 AC 106 ms
29,452 KB
testcase_34 AC 99 ms
29,548 KB
testcase_35 AC 102 ms
29,568 KB
testcase_36 AC 106 ms
29,452 KB
testcase_37 AC 46 ms
6,940 KB
testcase_38 AC 392 ms
95,884 KB
testcase_39 AC 392 ms
95,304 KB
testcase_40 AC 2 ms
6,944 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