boj 2365 - 숫자판 만들기

 

설명은 나중에...

 

#include <stdio.h>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

#define MAX_NODE (50 * 2 + 1)
#define START (MAX_NODE + 1)
#define END (START + 1)
#define MAX_SIZE (END + 1)
#define INFINITY_FLOW 99999
#define MIN(a, b) a < b? a: b
int N;
int SUM;
vector<int> adj[MAX_SIZE];
int flow[MAX_SIZE][MAX_SIZE];
int tmp_flow[MAX_SIZE][MAX_SIZE];
int max_val = 0;

int bfs(int start, int end) {
    queue<int> q;
    int parent[MAX_SIZE];
    int cur = 0;
    int min_flow = INFINITY_FLOW;
    bool found = false;

    memset(parent, -1, sizeof(int) * MAX_SIZE);
    q.push(start);

    while (!q.empty() && !found) {
        cur = q.front();
        q.pop();
        for (vector<int>::iterator itr = adj[cur].begin(); itr != adj[cur].end(); itr++) {
            if (parent[*itr] != -1 || tmp_flow[cur][*itr] == 0) {
                continue;
            }
            parent[*itr] = cur;
            if (*itr == end) {
                found = true;
                break;
            }
            q.push(*itr);
        }
    }
    
    if (!found) {
        return 0;
    }

    for(cur = end; cur!= start; cur = parent[cur]){
        min_flow = MIN(min_flow, tmp_flow[parent[cur]][cur]);
    }

    for(cur = end; cur!= start; cur = parent[cur]){
        tmp_flow[parent[cur]][cur] -= min_flow;
        tmp_flow[cur][parent[cur]] += min_flow;
    }

    return min_flow;
}

bool network_flow(int start, int end) {
    int flow_ret = 0;
    int flow_sum = 0;
    while ((flow_ret = bfs(start, end))) {
        flow_sum += flow_ret;
    }
    return flow_sum == SUM;
}

int binary_search(int start, int end) {
    int mid;
    const int RIGHT_START = N;

    while (start <= end) {
        mid = (start + end)/2;
        memcpy(tmp_flow, flow, sizeof(int) * MAX_SIZE * MAX_SIZE);
        for(int i = 0; i< RIGHT_START; i++) {
            for(vector<int>::iterator itr = adj[i].begin(); itr != adj[i].end(); itr++) {
                if (*itr == START)
                    continue;
                tmp_flow[i][*itr] = MIN(mid, tmp_flow[i][*itr]);
            }
        }
        if (network_flow(START, END)) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    
    return start;
}

void add_adj(int a, int b){
    adj[a].push_back(b);
    adj[b].push_back(a);
}

int main(){
    scanf("%d", &N);
    int tmp;
    const int RIGHT_START = N;

    for (int i=0; i<N; i++) {
        scanf("%d", &tmp);
        add_adj(START, i);
        flow[START][i] = tmp;

        SUM += tmp;
        max_val = tmp > max_val ? tmp : max_val;
    }
    for (int i=0; i<N; i++) {
        scanf("%d", &tmp);
        add_adj(RIGHT_START + i, END);
        flow[RIGHT_START + i][END] = tmp;
        max_val = tmp > max_val ? tmp : max_val;
    }

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            add_adj(i, RIGHT_START + j);
            flow[i][RIGHT_START + j] = MIN(flow[START][i], flow[RIGHT_START + j][END]);
        }
    }
    int ANS = binary_search(1, max_val);
    int final_check = 0;
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            final_check += tmp_flow[RIGHT_START+j][i];
        }
    }

    if (final_check != SUM) {
        binary_search(ANS, ANS);
    }

    printf("%d\n", ANS);
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            printf("%d ",tmp_flow[RIGHT_START+j][i]);
        }
        printf("\n");
    }
    return 0;
}