백준2365 숫자판 만들기

작성일 | In

문제 링크

  • http://icpc.me/2365

사용 알고리즘

  • 네트워크 플로우
  • 최대 유량
  • 파라메트릭 서치

풀이

1960 행렬 만들기와 비슷한 방식으로 풀 수 있는 문제입니다.(풀이)
행렬 만들기 풀이를 먼저 보고 와주세요.


소스(S)와 각 행을 대표하는 간선, 각 열을 대표하는 간선과 싱크(T)를 연결하는 간선의 capacity는 각각 행/열의 합으로 잡는 것은 동일합니다.
행렬 만들기 문제에서는 0 아니면 1이 들어가지만 이 문제에서는 0~10000의 자연수가 들어갈 수 있으면서, 가장 큰 숫자를 최소화해야 합니다.

가장 큰 숫자의 최솟값을 파라메트릭 서치로 찾아주면서, 행을 대표하는 정점과 열을 대표하는 정점을 잇는 간선의 capacity를 상한 제한값으로 잡아주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;

int c[111][111];
int f[111][111];
int bias = 50;
int n;
vector<int> g[111];
int par[111];

int a[55], b[55];
int asum, bsum;

int s = 101, t = 102;

void init(int x){
	memset(f, 0, sizeof f);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			c[i][j+bias] = x;
		}
	}
}

bool chk(int x){
	init(x);
	int res = 0;
	while(1){
		memset(par, -1, sizeof par);
		queue<int> q; q.push(s);
		while(q.size()){
			int now = q.front(); q.pop();
			for(auto nxt : g[now]){
				if(par[nxt] == -1 && c[now][nxt] - f[now][nxt] > 0){
					par[nxt] = now; q.push(nxt);
				}
			}
		}
		int flow = 1e9+7;
		if(par[t] == -1) break;
		for(int i=t; i!=s; i=par[i]){
			int a = par[i], b = i;
			flow = min(flow, c[a][b] - f[a][b]);
		}
		res += flow;
		for(int i=t; i!=s; i=par[i]){
			int a = par[i], b = i;
			f[a][b] += flow; f[b][a] -= flow;
		}
	}
	return asum == bsum && asum == res;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++) cin >> a[i], asum += a[i];
	for(int i=1; i<=n; i++) cin >> b[i], bsum += b[i];
	for(int i=1; i<=n; i++){
		g[s].push_back(i);
		c[s][i] = a[i];
		c[i+bias][t] = b[i];
		g[i+bias].push_back(t);
	}
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			g[i].push_back(j+bias);
			g[j+bias].push_back(i);
		}
	}

	int l = 0, r = 10000;
	int ans = -1;
	while(l <= r){
		int m = l + r >> 1;
		if(chk(m)){
			ans = m; r = m - 1;
		}else{
			l = m + 1;
		}
	}
	cout << ans << "\n";
	chk(ans);
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++){
			cout << f[i][j+bias] << " ";
		}
		cout << "\n";
	}
}