문제 백준 2365번 숫자판 만들기
https://www.acmicpc.net/problem/2365
놀랍게도 네트워크 플로우 문제이다.
풀이
마방진(?)같이 생긴것을 채워야한는데 아래 그림처럼 그래프로 만들어 버리자.
유량이 limit인 간선에 흐르는 유량이 마방진에 채워지는 숫자이다. 숫자의 합이 조건을 충족 시키려면 최대 유량이 16이어야 한다.
합이 조건을 충족 = 최대 유량이 16
최대 유량이 16이 되기 시작하는 limit값을 찾아주면 된다. limit의 최댓값은 10000이기 때문에 0부터 10000까지 이분탐색을 해주면 쉽게 구할 수 있다.
의사 코드
maxFlow < 16일때, 구간을 [mid+1, r]으로 변경
maxFlow == 16 일때, 구간을 [l, mid-1]으로 변경하고 답을 저장
코드
|
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
#include<bits/stdc++.h>
#define fio() \
ios_base::sync_with_stdio(0); \
cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int dx[] = { 0, 1, 0, –1 };
const int dy[] = { 1, 0, –1, 0 };
const double pi = acos(–1);
const int MOD = 1000000007;
int c[2020][2020], f[2020][2020];
int pre[2020];
vector<int> g[2020];
int arr[120][120], n;
void init(){
memset(c, 0, sizeof(c));
memset(f, 0, sizeof(f));
for(int i = 1; i <= n; i++){
c[0][i] = arr[0][i];
c[i+n][2*n+1] = arr[1][i];
}
}
int cal(int limit){
int res = 0;
const int s = 0;
const int e = 2*n+1;
init();
for(int i = 1; i <= n; i++){
for(int j = n+1; j <= 2*n; j++){
c[i][j] = limit;
}
}
while(1){
memset(pre, –1, sizeof(pre));
queue<int> q;
q.push(s);
while(!q.empty()){
int now = q.front();
q.pop();
for(int nxt : g[now]){
if(c[now][nxt]–f[now][nxt] > 0 && pre[nxt]== –1){
q.push(nxt);
pre[nxt] = now;
if(nxt == e) break;
}
}
}
if(pre[e] == –1) break;
int flow = INF;
for(int i = e; i != s; i = pre[i]){
flow = min(flow, c[pre[i]][i]–f[pre[i]][i]);
}
for(int i = e; i != s; i = pre[i]){
f[pre[i]][i] += flow;
f[i][pre[i]] –= flow;
}
res += flow;
}
return res;
}
int main(){
scanf(“%d”, &n);
for(int i = 0; i < 2; i++){
for(int j = 1; j <= n; j++){
scanf(“%d”, &arr[i][j]);
}
}
const int s = 0;
const int e = 2*n+1;
int maxFlow = 0;
for(int i = 1; i <= n; i++){
maxFlow += arr[0][i];
g[s].push_back(i);
g[i].push_back(s);
c[s][i] = arr[0][i];
for(int j = n+1; j <= 2*n; j++){
g[i].push_back(j);
g[j].push_back(i);
}
}
int f_ans[120][120];
for(int i = 1; i <= n; i++){
g[i+n].push_back(e);
g[e].push_back(i+n);
c[i+n][e] = arr[1][i];
}
int l = 0, r = 10000, ans = r;
while(l <= r){
int mid = l + r >> 1;
if(cal(mid) < maxFlow){
l = mid+1;
}
else{
r = mid–1;
ans = min(ans, mid);
for(int i = 1; i <= n; i++){
for(int j = n+1; j <= 2*n; j++){
f_ans[i][j] = f[i][j];
}
}
}
}
printf(“%d\n”, ans);
for(int i = 1; i <= n; i++){
for(int j = n+1; j <= 2*n; j++){
printf(“%d “, f_ans[i][j]);
}
printf(“\n”);
}
}
|
cs |
회고
이런 생각 어떻게함?
Leave a Reply
Your email is safe with us.