[백준] 11495 격자 0 만들기

문제

음수가 아닌 정수들의 격자가 주어진다. 당신은 이 격자에 다음 연산을 행할 수 있다.

• 1. 격자에서 가로 또는 세로로 인접한 정수 2개를 고른다.
• 2. 각 정수가 양수일 때 1 감소시킨다.

다음 그림은 총 4개의 연속한 연산을 2*2 격자에 가해서 모든 정수를 0으로 만든 과정을 보여준다.

위 예제에서는 모든 정수를 0으로 만들기 위해 4번의 연산을 행했다. 이보다 적은 횟수의 연산으로는 모든 정수를 0으로 만들 수 없다는 것을 쉽게 알 수 있다.

격자가 주어졌을 때 모든 정수를 0으로 만들기 위해 필요한 최소 연산의 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n과 m (2 ≤ n, m ≤ 50)이 주어지며, n은 격자의 행 개수, m은 격자의 열 개수를 나타낸다. 그 다음 n개의 줄에 각각 격자의 해당 행에 있는 m개의 정수가 열 순서대로 주어진다. 각 정수는 0 이상 1,000 이하이다.

출력

각 테스트 케이스마다 필요한 연산의 최소 횟수를 한 줄에 출력한다.

격자에서 가로,세로 한 쌍씩 묶어서 연산을 수행합니다.

이때 한 정점에 대해서는 그 정점의 숫자만큼 연산이 가능하고,

바로 옆에있는 정점과 같이 연산이 가능합니다.

따라서 격자무늬로 모델링이 가능합니다.

격자무늬로 모델링을하고, 소스또는 싱크에서 그 숫자만큼 capacity를 줍니다.

그리고 간선 간 함께 연산을 수행가능한 정점끼리 간선을 부여합니다.

이상태로 최대유량을 수행하고, 싱크또는 소스에서 capacity-flow(남는 간선)만큼만 더해주면 답입니다.

 

에드먼즈 카프 알고리즘으로 수행한 결과입니다.

#include<bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false),cin.tie(NULL);
#define mset(v) memset(v,0,sizeof(v));
#define rep(i,a) for(int i=0;i<a;++i)
#define REP(i,a) for(int i=1;i<=a;++i)

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int>ti;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
int dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, INF = 987654321, S = 3001, E = 3002, A, B = 1500;
vi adj[3003];
using namespace std;

int TC, N, M, x, idx[53][53], ans, c[3003][3003], f[3003][3003];
int main() {
	FAST;
	cin >> TC;
	while (TC--) {
		ans = 0;
		mset(idx);
		mset(c);
		mset(f);
		for (int i = 1; i <= 3002; i++) {
			adj[i].clear();
		}
		A = 0, B = 1500;
		cin >> N >> M;
		REP(i, N)REP(j, M) {
			cin >> x;
			if ((i + j) % 2 == 0) {
				idx[i][j] = ++A;
				c[S][A] = x;
				adj[S].push_back(A);
				adj[A].push_back(S);
			}
			else {
				idx[i][j] = ++B;
				c[B][E] = x;
				adj[B].push_back(E);
				adj[E].push_back(B);
			}
		}
		REP(i,N)REP(j,M){
			rep(k, 4) {
				int ny = i + dy[k];
				int nx = j + dx[k];
				if (ny >= 1 && ny <= N && nx >= 1 && nx <= M && (i+j)%2 == 0) {
					c[idx[i][j]][idx[ny][nx]] = INF;
					adj[idx[i][j]].push_back(idx[ny][nx]);
					adj[idx[ny][nx]].push_back(idx[i][j]);
				}
			}
		}
		while (1) {
			queue<int>q;
			q.push(S);
			int p[3003];
			fill(p, p + 3003, -1);
			while (!q.empty()) {
				int cur = q.front();
				q.pop();
				for (int nxt : adj[cur]) {
					if (p[nxt]==-1 && c[cur][nxt] - f[cur][nxt] > 0) {
						p[nxt] = cur;
						q.push(nxt);
					}
				}
			}
			if (p[E] == -1)break;
			int flow = INF;
			for (int i = E; i != S; i = p[i]) {
				flow = min(flow, c[p[i]][i] - f[p[i]][i]);
			}
			for (int i = E; i != S; i = p[i]) {
				f[p[i]][i] += flow;
				f[i][p[i]] -= flow;
			}
			ans += flow;
		}
		for (int i = 1; i <= A; i++) {
			ans += (c[S][i] - f[S][i]);
		}
		for (int i = 1501; i <= B; i++) {
			ans += (c[i][E] - f[i][E]);
		}
		cout << ans << "\n";
	}
}