boj 13161 - 분단의 슬픔

설명은 나중에...

 

굉장히 난이도가 높은 문제인 듯 싶다. 특히 dfs()를 최대한 잘 추려내지 않으면 대부분 timeout난다.

 

 

 

#include <stdio.h>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

#define MAX_FLOW 2147483646
#define NODE 500
#define SOURCE (NODE + 1)
#define SINK (SOURCE + 1)
#define MAX_NODE (SINK + 1)

vector<int> adj[MAX_NODE];
int flow[MAX_NODE][MAX_NODE];
int N;

bool bfs(int start, int end, int* level_graph) {
    queue<int> q;
    q.push(start);
    level_graph[start] = 0;

    while (!q.empty()) {
        int cur = q.front();
        if (cur == end) {
            return true;
        }
        q.pop();
        for (auto itr = adj[cur].begin(); itr != adj[cur].end(); itr++) {
            if(level_graph[*itr] != -1 || flow[cur][*itr] == 0) {
                continue;
            }
            level_graph[*itr] = level_graph[cur] + 1;
            q.push(*itr);
        }
    }
    return false;
}

int dfs(int cur, int end, int* level_graph, vector<int>::iterator* itr_save, int cur_flow) {
    if (cur == end) {
        return cur_flow;
    }
    for (auto itr = itr_save[cur]; itr != adj[cur].end(); itr++) {
        itr_save[cur] = itr;
        if(level_graph[*itr] != level_graph[cur] + 1 || flow[cur][*itr] == 0) {
            continue;
        }
        int min_flow = cur_flow < flow[cur][*itr] ? cur_flow : flow[cur][*itr];
        int ret_val = dfs(*itr, end, level_graph, itr_save, min_flow);
        if (ret_val > 0) {
            flow[cur][*itr] -= ret_val;
            flow[*itr][cur] += ret_val;
            return ret_val;
        }
    }
    return 0;
}
void print_parties(int start, int end) {
    int visited[MAX_NODE];
    memset(visited, -1, sizeof(int) * MAX_NODE);

    bfs(start, end, visited);
    for (int i=0; i<N; i++) {
        if(visited[i] != -1)
            printf("%d ", i+1);
    }
    printf("\n");
    for (int i=0; i<N; i++) {
        if(visited[i] == -1)
            printf("%d ", i+1);
    }
    printf("\n");
}

int dinic_algorithm(int start, int end) {
    int level_graph[MAX_NODE];
    memset(level_graph, -1, sizeof(int) * MAX_NODE);

    bool result = bfs(start, end, level_graph);
    if (result == false) {
        return 0;
    }
    int augmented = 0;
    int retval = 0;
    vector<int>::iterator itr_save[MAX_NODE];
    for (int i=0; i<MAX_NODE; i++) 
        itr_save[i] = adj[i].begin();
    
    do {
        retval = dfs(start, end, level_graph, itr_save, MAX_FLOW);
        augmented += retval;
    } while(retval);
    return augmented;
}

void add_edge(int a, int b, int forward_cost, int reverse_cost) {
    adj[a].push_back(b);
    adj[b].push_back(a);
    flow[a][b] = forward_cost;
    flow[b][a] = reverse_cost;
}

int main() {
    scanf("%d", &N);
    int tmp;
    for (int i=0; i<N; i++) {
        scanf("%d", &tmp);

        if (tmp == 1) {
            add_edge(SOURCE, i, MAX_FLOW, 0);
        } else if (tmp == 2) {
            add_edge(i, SINK, MAX_FLOW, 0);
        }
    }

    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            scanf("%d", &tmp);
            if (i >= j || tmp == 0)
                continue;
            add_edge(i, j, tmp, tmp);
        }
    }
    int ANS = 0;
    int augmented = 0;
    while ((augmented = dinic_algorithm(SOURCE, SINK)) > 0) {
        ANS += augmented;
    }
    printf("%d\n",ANS);
    print_parties(SOURCE, SINK);
    return 0;
}