(Elice / 최대유량 / C++) 가로합 세로합

가로합 세로합

엘리스와 친구들은 네모네모로직을 같이 풀고 있었습니다. 그런데 엘리스와는 달리 나머지 친구들은 네모네모로직을 잘 풀지 못해 엘리스는 친구들을 위해 네모네모로직을 변형한 가로합 세로합이란 게임을 만들었습니다.

가로합 세로합 게임은 다음과 같습니다. 가로의 크기와 세로의 크기가 각각 N인 숫자판이 있습니다. 각 칸에는 음이 아닌 정수들이 들어갑니다. 각 행과 각 열의 합이 미리 주어집니다. 아래는 N = 2의 예시입니다.

위 그림에서 숫자판 옆의 수는 해당하는 행에 들어가는 숫자의 합을 나타내며, 숫자판 아래의 수는 해당하는 열에 들어가는 숫자의 합을 나타냅니다.

위의 예시에서 들어갈 수 있는 숫자는 많지만, 물음표에 들어가는 최대 숫자의 값을 최소로 하는 숫자를 찾으려고 합니다. 위의 예에서는 최대 숫자가 8인 형태가 원하는 답입니다.

이 문제를 해결하는 프로그램을 작성하세요.

 

입력

• 입력의 첫째 줄에는 숫자판의 크기인 정수 N을 입력합니다.

                                             (1≤N≤50)

• 둘째 줄에는 N 개의 정수를 공백으로 구분하여 입력합니다. 주어지는 정수는 1행부터 N 행까지의 합을 차례대로 나타냅니다.
• 셋째 줄에는 N 개의 정수를 공백으로 구분하여 입력합니다. 주어지는 정수는 1열부터 N 열까지의 합을 차례대로 나타냅니다.
• 합을 나타내는 각 정수는 0 이상 1,000 이하입니다.
• 숫자판을 구성할 수 없는 입력은 주어지지 않는다고 가정합니다.

출력

• 첫째 줄에는 배정된 수들 중 최댓값을 출력합니다.
• 둘째 줄부터 (N+1) 째 줄까지 각 행에 배정된 수들을 한 줄에 한 행씩 출력합니다.
• 배정되는 각각의 정수는 0 이상이어야 합니다.

입력 예시

2
10 15
16 12

출력 예시

8
8 2 
8 7 

소스 코드

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 105
#define INF 1000000000

using namespace std;

int Sum;
int Capacity[MAX][MAX], Flow[MAX][MAX];
vector<int> Line[MAX];

int MaxFlow(int Sour, int Sink) {
    int FlowSum = 0;
    while(true) {
        int Parent[MAX] = {};
        queue<int> Queue;
        Queue.push(Sour);
        Parent[Sour] = Sour;
        while(!Queue.empty() && !Parent[Sink]) {
            int Cur = Queue.front();
            Queue.pop();
            for(int i=0; i<Line[Cur].size(); i++) {
                int Next = Line[Cur][i];
                if(Capacity[Cur][Next] - Flow[Cur][Next] > 0 && !Parent[Next]) {
                    Queue.push(Next);
                    Parent[Next] = Cur;
                    if(Next == Sink) break;
                }
            }
        }
        if(!Parent[Sink]) break;

        int Amount = INF;
        for(int i=Sink; i!=Sour; i=Parent[i])
            Amount = min(Amount, Capacity[Parent[i]][i] - Flow[Parent[i]][i]);
        for(int i=Sink; i!=Sour; i=Parent[i]) {
            Flow[Parent[i]][i] += Amount;
            Flow[i][Parent[i]] -= Amount;
        }
        FlowSum += Amount;
    }
    return FlowSum;
}

int main() {
    int N;
    scanf("%d", &N);
    int Sour = 2*N+1, Sink = 2*N+2;
    for(int i=1; i<=N; i++) {
        Line[Sour].push_back(i), Line[i].push_back(Sour);
        scanf("%d", &Capacity[Sour][i]);
        Sum += Capacity[Sour][i];
    }
    for(int i=N+1; i<=2*N; i++) {
        Line[i].push_back(Sink), Line[Sink].push_back(i);
        scanf("%d", &Capacity[i][Sink]);
    }
    for(int i=1; i<=N; i++)
        for(int j=N+1; j<=2*N; j++)
            Line[i].push_back(j), Line[j].push_back(i);
    int Left = 0, Right = 10000, Mid, Ans;
    while(Left <= Right) {
        Mid = (Left + Right)/2;
        for(int i=1; i<=N; i++)
            for(int j=N+1; j<=2*N; j++) Capacity[i][j] = Mid;
        fill(&Flow[0][0], &Flow[MAX-1][MAX], 0);
        if(MaxFlow(Sour, Sink) == Sum) {
            Ans = Mid;
            Right = Mid-1;
        }
        else Left = Mid+1;
    }
    printf("%d\n", Ans);

    for(int i=1; i<=N; i++)
        for(int j=N+1; j<=2*N; j++) Capacity[i][j] = Ans;
    fill(&Flow[0][0], &Flow[MAX-1][MAX], 0);
    MaxFlow(Sour, Sink);
    for(int i=1; i<=N; i++) {
        for(int j=N+1; j<=2*N; j++) printf("%d ", Flow[i][j]);
        printf("\n");
    }
}