[BOJ 2365 // C++] 숫자판 만들기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2365번 문제인 숫자판 만들기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/2365 

2365번: 숫자판 만들기

각 행과 각 열을 하나의 노드로 잡아 source에서 행 노드로 그 행의 총합을, 열 노드에서 sink로 그 열의 총합을, 각 행에서 각 열로의 용량을 K로 잡고 유량을 흘렸을 때 가능한 최대 유량이 흐르는 최소 K를 찾아 문제를 해결하자.

 

위의 탐색은 이분탐색을 이용하여 빠르게 진행할 수 있다.

 

아래는 제출한 소스코드이다.

#define NODE 102
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int source, sink;
int edge[NODE][NODE];
vector<int> G[NODE];
int level[NODE];

bool dinic_bfs() { // 현 단계의 level graph 생성; 리턴값: 성공여부
	memset(level, 0, sizeof(level));
	level[source] = 1;
	queue<int> que;
	que.push(source);
	while (!que.empty()) {
		int& cur = que.front();
		for (auto& node : G[cur]) {
			if (edge[cur][node] && level[node] == 0) {
				level[node] = level[cur] + 1;
				que.push(node);
			}
		}
		que.pop();
	}

	return level[sink];
}

int turn[NODE];

int dinic_dfs(int cur, int flow) { // flow값 오버플로우 주의
	if (cur == sink) return flow;
	int cursize = G[cur].size();
	for (int& i = turn[cur]; i < cursize; i++) {
		int& node = G[cur][i];
		if (edge[cur][node] && level[node] == level[cur] + 1) {
			int tmp = dinic_dfs(node, min(edge[cur][node], flow));
			if (tmp) {
				edge[cur][node] -= tmp;
				edge[node][cur] += tmp;
				return tmp;
			}
		}
	}

	return 0;
}

int dinic() { // 실제 maximum flow 계산
	int ret = 0;
	while (dinic_bfs()) {
		memset(turn, 0, sizeof(turn));
		int f;
		while (f = dinic_dfs(source, 1000000007)) ret += f;
	}

	return ret;
}

int N;
int R[51], C[51];
int totalR = 0, totalC = 0;

bool func(int k) {
	for (int c = 1; c <= N; c++) edge[source][c] = C[c], edge[c][source] = 0;
	for (int r = N + 1; r <= N * 2; r++) edge[r][sink] = R[r - N], edge[sink][r] = 0;

	for (int c = 1; c <= N; c++) {
		for (int r = N + 1; r <= N * 2; r++) {
			edge[c][r] = k;
			edge[r][c] = 0;
		}
	}

	return dinic() == totalR;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	source = 0, sink = 2 * N + 1;

	for (int c = 1; c <= N; c++) {
		cin >> C[c];
		totalC += C[c];
	}
	for (int r = 1; r <= N; r++) {
		cin >> R[r];
		totalR += R[r];
	}
	for (int c = 1; c <= N; c++) G[source].emplace_back(c), G[c].emplace_back(source);
	for (int r = N + 1; r <= N * 2; r++) G[r].emplace_back(sink), G[sink].emplace_back(r);

	for (int c = 1; c <= N; c++) {
		for (int r = N + 1; r <= N * 2; r++) {
			G[c].emplace_back(r);
			G[r].emplace_back(c);
		}
	}


	int low = 0, high = 10000;
	while (low < high) {
		int mid = (low + high) / 2;
		if (func(mid)) high = mid;
		else low = mid + 1;
	}

	func(low);
	cout << low << '\n';
	for (int c = 1; c <= N; c++) {
		for (int r = N + 1; r <= N * 2; r++) {
			cout << edge[r][c] << ' ';
		}
		cout << '\n';
	}
}