제출 #1247941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247941		dfhdfhdsf	Selotejp (COCI20_selotejp)	C++20	35 / 110	1 ms	584 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1e9;

struct HopcroftKarp {
    int nL, nR;
    vector<vector<int>> adj;
    vector<int> pairU, pairV, dist;

    HopcroftKarp(int _nL, int _nR)
      : nL(_nL), nR(_nR),
        adj(_nL+1),
        pairU(_nL+1, 0),
        pairV(_nR+1, 0),
        dist(_nL+1, 0)
    {}

    void addEdge(int u, int v){
        // u in [1..nL], v in [1..nR]
        adj[u].push_back(v);
    }

    bool bfs(){
        queue<int> q;
        // dist[0] is dist to NIL
        for(int u = 1; u <= nL; ++u){
            if(pairU[u] == 0){
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = INF;
            }
        }
        dist[0] = INF;
        while(!q.empty()){
            int u = q.front(); q.pop();
            if(dist[u] < dist[0]){
                for(int v : adj[u]){
                    if(dist[pairV[v]] == INF){
                        dist[pairV[v]] = dist[u] + 1;
                        q.push(pairV[v]);
                    }
                }
            }
        }
        return dist[0] != INF;
    }

    bool dfs(int u){
        if(u == 0) return true;
        for(int v : adj[u]){
            if(dist[pairV[v]] == dist[u] + 1){
                if(dfs(pairV[v])){
                    pairU[u] = v;
                    pairV[v] = u;
                    return true;
                }
            }
        }
        dist[u] = INF;
        return false;
    }

    int maxMatching(){
        int matching = 0;
        while(bfs()){
            for(int u = 1; u <= nL; ++u){
                if(pairU[u] == 0 && dfs(u)){
                    ++matching;
                }
            }
        }
        return matching;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }

    // 1) Đánh số segment ngang
    vector<vector<int>> hID(n, vector<int>(m, 0));
    int hCount = 0;
    for(int i = 0; i < n; ++i){
        int curr = 0;
        for(int j = 0; j < m; ++j){
            if(a[i][j] == '#'){
                if(curr == 0){
                    curr = ++hCount;
                }
                hID[i][j] = curr;
            } else {
                curr = 0;
            }
        }
    }

    // 2) Đánh số segment dọc
    vector<vector<int>> vID(n, vector<int>(m, 0));
    int vCount = 0;
    for(int j = 0; j < m; ++j){
        int curr = 0;
        for(int i = 0; i < n; ++i){
            if(a[i][j] == '#'){
                if(curr == 0){
                    curr = ++vCount;
                }
                vID[i][j] = curr;
            } else {
                curr = 0;
            }
        }
    }

    // 3) Xây đồ thị bipartite
    HopcroftKarp hk(hCount, vCount);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(a[i][j] == '#'){
                hk.addEdge(hID[i][j], vID[i][j]);
            }
        }
    }

    // 4) Kết quả = max matching = min vertex cover
    cout << hk.maxMatching() << "\n";
    return 0;
}

• Subtask 1: 35 / 35
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40