Submission #1247950

#TimeUsernameProblemLanguageResultExecution timeMemory
1247950dfhdfhdsfSelotejp (COCI20_selotejp)C++20
35 / 110
1 ms584 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define FOR(i,a,b) for(int i=(a); i<=(b); ++i) #define FORD(i,a,b) for(int i=(a); i>=(b); --i) #define isz(s) ((int)(s).size()) #define ALL(x) (x).begin(), (x).end() const int INF = 1e9; // Hopcroft–Karp cho đồ thị bipartite L = [1..nL], R = [1..nR] struct HopcroftKarp { int nL, nR; vector<vector<int>> adj; vector<int> dist, pairU, pairV; HopcroftKarp(int _nL, int _nR) : nL(_nL), nR(_nR), adj(_nL+1), dist(_nL+1), pairU(_nL+1, 0), pairV(_nR+1, 0) {} void addEdge(int u, int v) { adj[u].push_back(v); } bool bfs() { queue<int> q; FOR(u,1,nL) { 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 && dfs(pairV[v])) { pairU[u] = v; pairV[v] = u; return true; } } dist[u] = INF; return false; } int maxMatching() { int matching = 0; while (bfs()) { FOR(u,1,nL) { if (pairU[u] == 0 && dfs(u)) ++matching; } } return matching; } }; int n, m; vector<string> grid; void solve() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; grid.resize(n); FOR(i,0,n-1) { cin >> grid[i]; } // Gán ID cho các đoạn liên tiếp theo hàng (# runs) vector<vector<int>> h_id(n, vector<int>(m, 0)); int cntH = 0; FOR(i,0,n-1) FOR(j,0,m-1) { if (grid[i][j] == '#') { if (j == 0 || grid[i][j-1] == '.') ++cntH; h_id[i][j] = cntH; } } // Gán ID cho các đoạn liên tiếp theo cột vector<vector<int>> v_id(n, vector<int>(m, 0)); int cntV = 0; FOR(j,0,m-1) FOR(i,0,n-1) { if (grid[i][j] == '#') { if (i == 0 || grid[i-1][j] == '.') ++cntV; v_id[i][j] = cntV; } } // Xây dựng đồ thị bipartite H (1..cntH) – V (1..cntV) HopcroftKarp hk(cntH, cntV); FOR(i,0,n-1) FOR(j,0,m-1) { if (grid[i][j] == '#') { hk.addEdge(h_id[i][j], v_id[i][j]); } } // Kết quả = kích thước maximum matching cout << hk.maxMatching() << "\n"; } int main() { solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...