10937 두부 모판 자르기 https://www.acmicpc.net/problem/10937
2차원 배열이 주어진다.
배열에서 가로또는 세로로 인접한 정수 2개를 고른 후 양수 이면 각각 1씩 감소시킨다.
위의 연산으로 모든 배열을 0으로 만들 최소 연산 수를 구하는 문제이다.
flow문제는 정말 생각을 많이 해야되는것 같다.
처음에는 flow인것 같지도 않다가 감이 왔어도 모델링하는게 쉽지 않다.
모델링을 다음과 같이 하면 해결할 수 있다.
유량이 0이 되지 않은 남은 정점들의 합이 최소 연산수가 된다.
(그림은 '라이'님 블로그에서 가져왔습니다.)
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define INF 987654321
int N, M;
int src, sink;
int arr[51][51];
int dy[] = { -1,0,0,1 };
int dx[] = { 0,-1,1,0 };
vector<vector<int>> adj;
int f[2555][2555], C[2555][2555];
void add_edge(int u, int v, int c) {
adj[u].emplace_back(v);
adj[v].emplace_back(u);
C[u][v] = c;
}
int max_flow() {
int ret = 0;
while (1) {
queue<int> q;
vector<int> par(N*M + 10, -1);
q.push(src);
while (!q.empty()) {
int here = q.front();
q.pop();
for (int next : adj[here]) {
if (C[here][next] - f[here][next] > 0 && par[next] == -1) {
par[next] = here;
q.push(next);
}
}
}
if (par[sink] == -1) break;
int flow = INF;
for (int i = sink; i != src; i = par[i])
flow = min(flow, C[par[i]][i] - f[par[i]][i]);
for (int i = sink; i != src; i = par[i])
f[par[i]][i] += flow, f[i][par[i]] -= flow;
ret += flow;
}
return ret;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int sum = 0;
memset(C, 0, sizeof C);
memset(f, 0, sizeof f);
scanf("%d%d", &N, &M);
adj = vector<vector<int>>(N*M + 10, vector<int>());
src = N*M + 8, sink = N*M + 9;
for (int n = 0;n < N;n++)
for (int m = 0;m < M;m++) scanf("%d", &arr[n][m]), sum += arr[n][m];
for (int n = 0;n < N;n++) {
for (int m = 0;m < M;m++) {
if ((!(n & 1) && !(m & 1)) || ((n & 1) && (m & 1))) { //둘다 짝 or 홀인 경우
add_edge(src, n*M + m, arr[n][m]);
for (int i = 0;i < 4;i++) {
int ny = n + dy[i], nx = m + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
add_edge(n*M + m, ny*M + nx, INF);
}
}
else add_edge(n*M + m, sink, arr[n][m]);
}
}
int ans = max_flow();
int plus = 0;
for (int n = 0;n < N;n++) {
for (int m = 0;m < M;m++) {
if ((!(n & 1) && !(m & 1)) || ((n & 1) && (m & 1))) //둘다 짝 or 홀인 경우
plus += C[src][n*M + m] - f[src][n*M + m];
else plus += C[n*M + m][sink] - f[n*M + m][sink];
}
}
printf("%d\n", ans + plus);
}
return 0;
}
| cs |
두부 모판 자르기도 비슷한 문제이다.
두부를 두칸 단위로 자를 수 있다.
두부의 품질표가 주어지고 모판이 주어질 때 두부를 잘라서 만들 수 있는 최대 가격을 구하는 문제다.
각 간선의 용량을 1로 하여 위와같이 모델링을 구성한다.
그리고 중앙에 간선의 cost를 두부의 품질로 하여 mcmf를 돌려주면 된다.
여기서 mcmf는 maximum cost가 되므로 부호를 반대로 주면 된다.
틀렸던 중요한 점이 있는데 위 문제와는 다르게 매칭이 안되는 경우도 있으므로 sink로도 이어준다.
위의 작업을 하지 않았을 때 다음의 반례 데이터가 존재한다.
5
ABCFC
ACCAB
FCAFB
BCABF
CCFAB
오른쪽이 정답이고 왼쪽에서 마지막 추가 유량에 20이 들어가는것을 볼 수 있다.
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 987654321
int N;
char map[12][12];
vector<int> adj[222];
int C[222][222], f[222][222], d[222][222];
const int src = 220, sink = 221;
int cost[4][4] = { {100,70,40,0},{70,50,30,0},{40,30,20,0},{0,0,0,0} };
int dy[] = { -1,0,0,1 };
int dx[] = { 0,1,-1,0 };
bool chk(int y, int x) {
if (y < 0 || y >= N || x < 0 || x >= N) return false;
return true;
}
int getcost(char c1, char c2) {
int i, j;
if (c1 == 'A') i = 0;
else if (c1 == 'B') i = 1;
else if (c1 == 'C') i = 2;
else i = 3;
if (c2 == 'A') j = 0;
else if (c2 == 'B') j = 1;
else if (c2 == 'C') j = 2;
else j = 3;
return cost[i][j];
}
void add_edge(int u, int v, int c, int dd) {
adj[u].push_back(v);
adj[v].push_back(u);
C[u][v] = c;
d[u][v] = dd;
d[v][u] = -dd;
}
int mcmf() {
int ret = 0;
while (1) {
queue<int> q;
vector<int> par(222, -1);
vector<bool> inQ(222, false);
vector<int> dist(222, INF);
dist[src] = 0;
q.push(src);
inQ[src] = true;
while (!q.empty()) {
int here = q.front();
q.pop();
inQ[here] = false;
for (int next : adj[here]) {
if (C[here][next] - f[here][next] > 0 && dist[next] > dist[here] + d[here][next]) {
par[next] = here;
dist[next] = dist[here] + d[here][next];
if (!inQ[next]) {
inQ[next] = true;
q.push(next);
}
}
}
}
if (par[sink] == -1) break;
int plus = 0;
for (int i = sink;i != src;i = par[i]) {
plus += d[par[i]][i];
f[par[i]][i]++, f[i][par[i]]--;
}
ret += plus;
}
return ret;
}
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf("%s", &map[n]);
for (int n = 0;n < N;n++) {
for (int m = 0;m < N;m++) {
if (!((n + m) & 1)) {
for (int i = 0;i < 4;i++) {
int y = n + dy[i], x = m + dx[i];
if (!chk(y, x)) continue;
add_edge(n*N + m, y*N + x, 1, -getcost(map[n][m], map[y][x]));
}
add_edge(n*N + m, sink, 1, 0); //매칭이 안되는 경우도 있으므로 sink로 이어준다.
add_edge(src, n*N + m, 1, 0);
}
else add_edge(n*N + m, sink, 1, 0);
}
}
printf("%d\n", -mcmf());
return 0;
}
| cs |
댓글 없음:
댓글 쓰기