백준[baekjoon] 2365

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

2365번: 숫자판 만들기

[문제설명]

- N*N 숫자판(숫자판의 수들은 주어지지 않음)의 N개의 행과 N개의 열의 합이 주어진다.

- 숫자판의 배정된 수들은 0이상의 정수이다.

- 조건을 만족하는 배정된 수 중에서 최댓값을 최소로 하는 숫자판을 찾아야한다.

 

[문제풀이]

- 지문에서 주어지는 입력을 시각화하면 아래와 같습니다.

c* = max(a, b, c, d)일때 c*의 값을 최소로하는 숫자판의 형태를 찾아야 합니다.

 

- 위 입력예시를 흐름 네트워크로 시각화해보면 아래와 같습니다.

문제의 조건을 충족시키기 위해 각 row의 합들은 src로 부터 간선을 이어주고, col의 합들은 sink로 간선을 이어줍니다.

숫자판 원소 최댓값(c*)을 이분탐색하여 row -> col 간선의 capacity로 설정하고, 최대유량값을 통해 숫자판을 구성할 수 있는지 확인해보면 됩니다.

 

- 주의할 점으로는 이분탐색이 끝난 후 흐름 네트워크가 숫자판 구성을실패한 case일 수 있으니 구한 최소 최댓값을 capacity로 설정하여 다시한번 흐름네트워크를 구성해주어야 합니다.

- 최대유량은 디니츠 알고리즘을 사용하였습니다.

 

[코드]

#include<bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX_N = 50 + 2;
const int MAX_V = 2*MAX_N;
const int S = MAX_V - 1;
const int E = MAX_V - 2;

typedef struct Edge {
	int to, c, cc, f;
	Edge* rev;
	Edge(int _to, int _c) : to(_to), c(_c){
		cc = c;
	}

	int spare() 
	{
		return c - f;
	}

	void addFlow(int flow)
	{
		f += flow;
		rev->f -= flow;
	}
} Edge;

int n, level[MAX_V], cache[MAX_V], row[MAX_N], col[MAX_N], tot;
vector<Edge*> adj[MAX_V];

void addEdge(int u, int v, int c)
{
	Edge *e1 = new Edge(v, c);
	Edge *e2 = new Edge(u, 0);

	e1->rev = e2;
	e2->rev = e1;

	adj[u].emplace_back(e1);
	adj[v].emplace_back(e2);
}

bool bfs()
{
	memset(level, -1, sizeof(level));
	queue<int> q;

	level[S] = 0;
	q.push(S);
	while(!q.empty()) {
		int cur = q.front(); q.pop();
		for(auto& e : adj[cur]) if(level[e->to] == -1 && e->spare()) {
			level[e->to] = level[cur] + 1;
			q.push(e->to);
		}
	}

	return level[E] != -1;
}

int dfs(int cur, int dest, int flow)
{
	if(cur == dest) return flow;

	for(int& i = cache[cur]; i<adj[cur].size(); ++i) {
		Edge* e = adj[cur][i];
		if(level[e->to] == level[cur] + 1 && e->spare()) {
			int f = dfs(e->to, dest, min(flow,e->spare()));
			
			if(f > 0) {
				e->addFlow(f);
				return f;
			}
		}
	}

	return 0;
}

bool check(int l)
{
	for(auto&v : adj) {
		for(auto& e : v) {
			e->f = 0;

			if(e->to >= n && e->to <2*n && e->cc > 0) {
				e->c = min(e->cc, l);
			}
		}
	}

	int amt = 0;
	while(bfs())
	{
		memset(cache, 0, sizeof(cache));
		while(1) {
			int flow = dfs(S, E, INF);
			if(flow == 0) break;

			amt += flow;
		}
	}

	return amt == tot;
}

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

	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> row[i];
		addEdge(S, i, row[i]);
		tot += row[i];
	}
	for(int i=0; i<n; ++i) {
		cin >> col[i];
		addEdge(n+i, E, col[i]);
	}

	for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) {
		addEdge(i, n+j, min(row[i], col[j]));
	}

	int s = -1, e = 1e4 + 1; // (s..e]
	while(e-s > 1) {
		int m = (s + e) >> 1;
		if(check(m)) e = m;
		else s = m;
	}

	check(e);
	cout << e << '\n';
	for(int i=0; i<n; ++i) {
		for(int j=0; j<n; ++j) {
			for(auto& e : adj[i]) if(e->to == n+j) {
				cout << e->f << ' ';
			}
		}
		cout << '\n';
	}
	return 0;
}