Buổi hòa nhạc

Điểm: 800 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

heygnauq

Dạng bài

Ngôn ngữ cho phép

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, PyPy, Python, Racket, Ruby, Rust, Scala, Scheme, ~~Scratch~~, Sed, ~~Swift~~, TCL, Turing, VB, Zig

Buổi hòa nhạc của lamter có $N \times M$ chỗ ngồi và $\frac{N \times M}{2}$ cặp đôi đến tham dự. Chỗ ngồi của họ đã được đặt trước.

Tuy nhiên một vài người họ đã không hài lòng và đã đề nghị đổi vị trí với nhau sao cho cặp đôi nào cũng được ngồi gần nhau. Một cặp đôi được gọi là ngồi gần nhau khi họ ngồi cạnh nhau cùng hàng hoặc ngồi cạnh nhau cùng cột.

Để đảm bảo trật tự cho buổi hòa nhạc bạn hãy giúp họ chọn ra số người ít nhất được đổi chỗ để cặp đôi nào cũng được ngồi gần nhau.

$Input$

Dòng đầu tiên chứa hai số nguyên $N$ và $M$ là kích thước của khán đài.
$N$ dòng tiếp theo mỗi dòng chứa $M$ số nguyên $x$ ( $1 \leq x \leq \frac{N \times M}{2}$ ), các cặp đôi được biểu thị bởi các số nguyên giống nhau.

$Output$

Gồm một dòng duy nhất là số người tối thiểu cần được đổi chỗ.

$Constraint$

$N$ , $M \leq 80$ .
Dữ liệu đảm bảo không có ai phải đi một mình.

$Subtask$

Subtask $1 (30 %)$ : $N$ , $M \leq 8$ .
Subtask $2 (70 %)$ : Không có giới hạn gì thêm.

$Sample Input$

Copy

$Sample Output$

Copy

$Note$

Các vị trí cần đổi chỗ là $(2, 1)$ , $(2, 2)$ , $(4, 2)$ , $(4, 3)$ .

Bình luận

Hãy đọc nội quy trước khi bình luận.

0
vandung666 đã bình luận 4:12:25 sa, 17/02/2025
include <iostream>

include <vector>

include <cstring>

include <algorithm>

define INF 1e9

const int MAXN = 80 * 80 + 5; int N, M; int grid[80][80]; int idx[80][80]; int n, m; std::vector<int> adj[MAXN]; int cost[MAXN][MAXN];

int lx[MAXN], ly[MAXN]; int slack[MAXN]; int match[MAXN]; bool visx[MAXN], visy[MAXN];

bool dfs(int x) { visx[x] = true; for (int y : adj[x]) { if (visy[y]) continue; int delta = lx[x] + ly[y] - cost[x][y]; if (delta == 0) { visy[y] = true; if (match[y] == -1 || dfs(match[y])) { match[y] = x; return true; } } else { slack[y] = std::min(slack[y], delta); } } return false; }

int KM() { memset(match, -1, sizeof(match)); memset(ly, 0, sizeof(ly)); for (int x = 0; x < n; ++x) { lx[x] = -INF; for (int y : adj[x]) { lx[x] = std::max(lx[x], cost[x][y]); } } for (int x = 0; x < n; ++x) { std::fill(slack, slack + m, INF); while (true) { memset(visx, 0, sizeof(visx)); memset(visy, 0, sizeof(visy)); if (dfs(x)) break; int d = INF; for (int y = 0; y < m; ++y) { if (!visy[y]) d = std::min(d, slack[y]); } for (int i = 0; i < n; ++i) { if (visx[i]) lx[i] -= d; } for (int y = 0; y < m; ++y) { if (visy[y]) ly[y] += d; else slack[y] -= d; } } } int result = 0; for (int y = 0; y < m; ++y) { if (match[y] != -1) { result += cost[match[y]][y]; } } return -result; }

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

Copy
std::cin >> N >> M; n = 0; m = 0; memset(cost, 0, sizeof(cost)); for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { std::cin >> grid[i][j]; if ((i + j) % 2 == 0) { idx[i][j] = n++; } else { idx[i][j] = m++; } } } int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; for (int i = 0; i < N; ++i){ for (int j = 0; j < M; ++j){ if ((i + j) % 2 == 0) { int u = idx[i][j]; for (int k = 0; k < 4; ++k){ int ni = i + dx[k], nj = j + dy[k]; if (ni >= 0 && ni < N && nj >= 0 && nj < M && ((ni + nj) % 2 == 1)) { int v = idx[ni][nj]; int c = (grid[i][j] == grid[ni][nj]) ? 0 : -1; adj[u].push_back(v); cost[u][v] = c; } } } } } int answer = KM(); std::cout << answer << "\n"; return 0;

} code cho minhtriet

-1

minhtriet17032008 đã bình luận 5:16:52 ch, 31/08/2024

Xin sol bài này với mọi người :((

0
vandung666 đã bình luận 9:04:11 sa, 17/02/2025
include <iostream>

include <vector>

include <cstring>

include <algorithm>

define INF 1e9

const int MAXN = 80 * 80 + 5; int N, M; int grid[80][80]; int idx[80][80]; int n, m; std::vector<int> adj[MAXN]; int cost[MAXN][MAXN];

int lx[MAXN], ly[MAXN]; int slack[MAXN]; int match[MAXN]; bool visx[MAXN], visy[MAXN];

bool dfs(int x) { visx[x] = true; for (int y : adj[x]) { if (visy[y]) continue; int delta = lx[x] + ly[y] - cost[x][y]; if (delta == 0) { visy[y] = true; if (match[y] == -1 || dfs(match[y])) { match[y] = x; return true; } } else { slack[y] = std::min(slack[y], delta); } } return false; }

int KM() { memset(match, -1, sizeof(match)); memset(ly, 0, sizeof(ly)); for (int x = 0; x < n; ++x) { lx[x] = -INF; for (int y : adj[x]) { lx[x] = std::max(lx[x], cost[x][y]); } } for (int x = 0; x < n; ++x) { std::fill(slack, slack + m, INF); while (true) { memset(visx, 0, sizeof(visx)); memset(visy, 0, sizeof(visy)); if (dfs(x)) break; int d = INF; for (int y = 0; y < m; ++y) { if (!visy[y]) d = std::min(d, slack[y]); } for (int i = 0; i < n; ++i) { if (visx[i]) lx[i] -= d; } for (int y = 0; y < m; ++y) { if (visy[y]) ly[y] += d; else slack[y] -= d; } } } int result = 0; for (int y = 0; y < m; ++y) { if (match[y] != -1) { result += cost[match[y]][y]; } } return -result; }

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

Copy
std::cin >> N >> M; n = 0; m = 0; memset(cost, 0, sizeof(cost)); for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { std::cin >> grid[i][j]; if ((i + j) % 2 == 0) { idx[i][j] = n++; } else { idx[i][j] = m++; } } } int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; for (int i = 0; i < N; ++i){ for (int j = 0; j < M; ++j){ if ((i + j) % 2 == 0) { int u = idx[i][j]; for (int k = 0; k < 4; ++k){ int ni = i + dx[k], nj = j + dy[k]; if (ni >= 0 && ni < N && nj >= 0 && nj < M && ((ni + nj) % 2 == 1)) { int v = idx[ni][nj]; int c = (grid[i][j] == grid[ni][nj]) ? 0 : -1; adj[u].push_back(v); cost[u][v] = c; } } } } } int answer = KM(); std::cout << answer << "\n"; return 0;

} day la y tuong cua mik cho tham khao