boj 11495 - 격자 0 만들기

설명은 나중에...

 

 

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>

#define CORE_NODE 2500
#define SOURCE_NODE (CORE_NODE + 1)
#define SINK_NODE (SOURCE_NODE + 1)
#define MAX_NODE (SINK_NODE + 1)
#define INF 999999
using namespace std;

vector<int> graph[MAX_NODE];
int flow[MAX_NODE][MAX_NODE];
int n, m;
int arr[50][50];

int bfs(int src, int dst)
{
	int parent[MAX_NODE], cur;
	queue<int> q;
	memset(parent, -1, sizeof(parent));

	q.push(src);
    parent[src] = -2;
	while (!q.empty()) {
		cur = q.front();
		q.pop();

		if (cur == dst) {
			break;
		}

		for (vector<int>::iterator itr = graph[cur].begin(); itr != graph[cur].end(); itr++) {
			if (parent[*itr] == -1 && flow[cur][*itr] > 0) {
				parent[*itr] = cur;
				q.push(*itr);
			}
		}
	}

	if (parent[dst] == -1)
		return 0;

	int min_flow = INF;
	while (cur != src) {
		if (min_flow > flow[parent[cur]][cur]) {
			min_flow = flow[parent[cur]][cur];
		}
		cur = parent[cur];
	}

	cur = dst;
	while (cur != src) {
		flow[parent[cur]][cur] -= min_flow;
		flow[cur][parent[cur]] += min_flow;
		cur = parent[cur];
	}
	return min_flow;
}

void make_adj(int src, int dst, int cost)
{
	graph[src].push_back(dst);
	graph[dst].push_back(src);
	flow[src][dst] = cost;
	flow[dst][src] = 0;
}

int testcase()
{
	int ans = 0;
	int ret = 0;
    int sum = 0;
	// input
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d ", &arr[i][j]);
            sum += arr[i][j];
		}
	}

	// create graph
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int tmp = i * m + j;
			if ((j + i) % 2 == 0) {
				make_adj(SOURCE_NODE, tmp, arr[i][j]);

				if (j > 0)  //left
					make_adj(tmp, tmp - 1, INF);
				if (j < m - 1) //right
					make_adj(tmp, tmp + 1, INF);
				if (i > 0) //up
					make_adj(tmp, tmp - m, INF);
				if (i < n - 1) //down
					make_adj(tmp, tmp + m, INF);

			} else {
				make_adj(tmp, SINK_NODE, arr[i][j]);
			}
		}
	}
	while ((ret = bfs(SOURCE_NODE, SINK_NODE))) {
		ans += ret;
	}
	return sum - ans;
}

void init_variable()
{
	n = m = 0;
	for(int i = 0; i < MAX_NODE; i++)
		graph[i].clear();

    for(int i = 0; i < MAX_NODE; i++)
        for(int j = 0; j < MAX_NODE; j++)
            flow[i][j] = 0;
}

int main()
{
	int T;
	scanf("%d", &T);
	for (int tc = 0; tc < T; tc++) {
		init_variable();
		printf("%d\n", testcase());
	}
	return 0;
}