블로그 옮겼습니다

BOJ 2365번 숫자판 만들기 본문

Algorithm/Problem Solving

BOJ 2365번 숫자판 만들기

sgc109 2017. 7. 14. 21:53

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









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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
struct edge{int to, cap, rev;};
int N;
int IN(int x){
    return x;
}
int OUT(int x){
    return x + 1;
}
int CELL(int i, int j){
    return 2 + 2 * N + 2 * (i * N + j);
}
int ROWSUM(int i){
    return 2 + i;
}
int COLSUM(int j){
    return 2 + N + j;
}
vector<edge> G[5200];
void connect(int from, int to, int cap){
    G[from].push_back(edge{to, cap, (int)G[to].size()});
    G[to].push_back(edge{from, 0, (int)G[from].size()-1});
}
 
int a, sum;
int rowsum[5200], colsum[5200];
int ans[53][53];
 
void makeGraph(int src, int sink, int limit){
    for(int i = 0 ; i < 5200; i++) G[i].clear();
    for(int i = 0 ; i < N; i++){
        for(int j = 0 ; j < N; j++){
            connect(IN(CELL(i, j)), OUT(CELL(i, j)), limit);
        }
    }
    for(int i = 0 ; i < N; i++){
        for(int j = 0 ; j < N; j++){
            connect(OUT(CELL(i, j)), ROWSUM(i), INF);
        }
    }
    for(int j = 0 ; j < N; j++){
        for(int i = 0 ; i < N; i++){
            connect(COLSUM(j), IN(CELL(i, j)), INF);
        }
    }
    for(int i = 0 ; i < N; i++) connect(src, COLSUM(i), colsum[i]);
    for(int i = 0 ; i < N; i++) connect(ROWSUM(i), sink, rowsum[i]);
}
int main() {
    int src = 0, sink = 1;
 
    cin >> N;
    for(int i = 0 ; i < N; i++cin >> rowsum[i];
    for(int i = 0 ; i < N; i++cin >> colsum[i];
    for(int i = 0 ; i < N; i++) sum += rowsum[i];
 
    int lo = 0, hi = 10001;
    while(lo < hi){
        int mid = (lo + hi)/2;
        makeGraph(src, sink, mid);
        Dinic d(G, 5200, src, sink);
        int maxflow = d.getMaxflow();
        if(maxflow == sum) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << endl;
 
    makeGraph(src, sink, lo);
    Dinic dinic(G, 5200, src, sink);
    dinic.getMaxflow();
    vector<vector<edge> > graph = dinic.getGraph();
 
    for(int i = 0 ; i < 5200; i++){
        for(auto e : graph[i]){
            int j = e.to;
            if(i == src || i == sink || j == src || j == sink) continue;
            if(i + 1 != j) continue;
            int num = (i - 2 - 2*N)/2;
            ans[num/N][num%N] = lo - e.cap;
        }
    }
 
    for(int i = 0 ; i < N; i++){
        for(int j = 0 ; j < N; j++){
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
 
    return 0;
}    
cs

<디닉을 클래스로 만들어 놓았다고 가정한 코드>

Comments