[BOJ 11495] 격자 0 만들기

문제 출처 : https://www.acmicpc.net/problem/11495

11495번: 격자 0 만들기

 

풀이 :

 

네트워크 플로우 최대 유량 문제입니다.

 

아래의 그림처럼 격자를 체스판처럼 나눠서 

Source -> 빨간색 영역 -> 사방의 하얀색 영역 -> Sink

이런식으로 모델링 해 주시면 가로 세로 블럭에 대한 모델링은 완성입니다.

 

 

그 다음 최소 연산 횟수를 구해야 하는데

위의 모델링으로 구할 수 있는 연산 횟수는 

" 둘다 양수인 격자에 대한 최소 연산 횟수 " 입니다.

따라서 양수와 0이 묶인 격자에 대한 처리는 하지 않은 상태입니다.

이에 대한 추가 연산을 해주어야하는데

 

Maximum Flow 를 F라 두었을때,

전체 격자판의 합 sum 에서 2F를 빼면 양수와 0이 묶인 격자에 대한 연산횟수만 남게됩니다.

 

예를 들면

 

1 1 1

1 0 1

 

인 격자판에서의 최대 유량은 2가 될것입니다.

sum - 2F = 1

따라서 0과 정수가 묶인 격자에 대한 연산횟수는 1이 됩니다.

 

0과 정수가 묶인 격자에 대한 연산횟수를 X라 두었을때, 위의 식을 고쳐 쓰면

sum - 2F = X

sum - F = X + F

가 됩니다.

 

따라서 격자를 0으로 만들기 위한 최소 연산 횟수는 전체 격자판의 합(sum) - MaximumFlow(F) 가 됩니다.

 

 

	#include<iostream>
	#include<algorithm>
	#include<vector>
	#include<queue>
	#define ms 2502
	using namespace std;
	struct MF {
	struct edge {
	int to, c, f;
	edge *d;
	edge(int to1 = -1, int c1 = 0) :to(to1), c(c1), f(0), d(nullptr) {}
	int spare() { return c - f; }
	void addFlow(int f1) {
	f += f1;
	d->f -= f1;
	}
	};
	int S = 0, E = ms - 1, mf = 0, t, n, m, map[50][50];
	vector<edge*>adj[ms];
	void init() {
	for (int i = 0; i < ms; i++)adj[i].clear();
	mf = 0;
	}
	void addEdge(int u, int v, int c) {
	edge *e1 = new edge(v, c), *e2 = new edge(u, 0);
	e1->d = e2;
	e2->d = e1;
	adj[u].push_back(e1);
	adj[v].push_back(e2);
	}
	int solve() {
	while (1) {
	int pre[ms];
	for (int i = 0; i < ms; i++)pre[i] = -1;
	edge* path[ms] = { 0 };
	queue<int> q;
	q.push(S);
	while (!q.empty()) {
	int now = q.front();
	q.pop();
	for (edge *e : adj[now]) {
	int next = e->to;
	if (pre[next] == -1 && e->spare() > 0) {
	pre[next] = now;
	path[next] = e;
	q.push(next);
	if (next == E)break;
	}
	}
	}
	if (pre[E] == -1)break;
	int flow = 1e9;
	for (int i = E; i != S; i = pre[i])flow = min(flow, path[i]->spare());
	for (int i = E; i != S; i = pre[i])path[i]->addFlow(flow);
	mf += flow;
	}
	return mf;
	}
	void inp() {
	cin >> t;
	while (t--) {
	init();
	cin >> n >> m;
	int sum = 0;
	for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)cin >> map[i][j], sum += map[i][j];
	for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) {
	int now = i * m + j + 1;
	if ((i + j) % 2) {
	addEdge(now, E, map[i][j]);
	continue;
	}
	addEdge(S, now, map[i][j]);
	if (i - 1 >= 0)addEdge(now, now - m, map[i - 1][j]);
	if (i + 1 < n)addEdge(now, now + m, map[i + 1][j]);
	if (j - 1 >= 0)addEdge(now, now - 1, map[i][j - 1]);
	if (j + 1 < m)addEdge(now, now + 1, map[i][j + 1]);
	}
	cout << sum - solve() << '\n';
	}
	}
	};
	int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	MF m;
	m.inp();
	}

view raw 11495.cpp hosted with ❤ by GitHub