백준 1210번: 마피아 (C++)

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

1210번: 마피아

---

Solved By: MFMC

 

각 정점에 대해 cost가 있기 때문에 Max Flow를 흘리기 위해 Edge의 비용은 INF로 처리하고, 정점 분할을 사용하여 in과 out사이에 비용을 할당하여 네트워크 모델링을 해야 했습니다.

 

1)

이번 문제에서 헷갈리면서 풀었던 것이 in에는 들어가기만 해야 하기 때문에 다른 node out으로 in을 인접 배열로 연결만 해주고, capacity값을 부여하면 안 됩니다. 연결만 해주는 이유는 역방향 간선 때문입니다.

 

2)

그리고, 이번 문제의 핵심은 Min Cut에 해당하는 정점들이 무엇인지를 찾는 것이었습니다.

첫 시도에서는 어떻게 찾았냐면 모든 정점을 확인하며 분할된 in에서 out으로의 capacity와 flow가 같은 것을 찾았습니다.

이 정점들이 Min Cut의 조건에 해당되기는 하지만 Min Cut 후보일 수도 있습니다.

 

왜냐하면 A, B node가 있을 때, A에서 B로 유량이 흐르고, A와 B의 capacity가 같다고 가정하면 흐르는 flow도 같습니다. 이러면 A node가 Min Cut입니다. B node에도 똑같이 흐르기 때문에 B의 capacity와 flow가 같아집니다. 이렇다고 해서 B는 minCut이 될 수 없습니다. 이미 A node에서 막혔기 때문입니다.

즉, Fully Saturated Node라고 답이 무조건 될 수는 없는 겁니다. 이러한 반례 때문에 capacity와 flow가 같은 것을 찾으면 안 됩니다.

 

방법은 BFS를 돌리면서 Residual Capacity가 남아있다면 next 정점을 체크하면서 넘어갑니다. 그러면서 in은 check가 되어있고, out이 check가 되어있지 않다면 Min Cut으로 판단하는 겁니다.

 

1)에서 모델링을 제대로 하지 않아서 BFS를 돌려도 답이 제대로 나오지 않아 어려움을 겪었습니다. -> 역방향 간선 갱신

 

이번 문제를 통해 Edmonds Karp에 대해 미흡한 점이 있는 게 아닌가 생각했습니다.

 

게다가 BFS를 메인에서 코드를 작성하니 오류가 나더군요. (맞히고 나서 틀렸던 코드들은 왜 틀렸나 디버깅하던 중 알았습니다. 선언된 변수나 자료 구조 중 이름이 겹치는 게 있나 싶어서 봤더니 그것도 딱히 아닌 거 같더군요. 함수를 사용하는 버릇을 들여야겠습니다. 왜인지는 아직 모르겠네요. 심지어 메인에서 BFS를 작성했을 때 !check[next]나 check[next] == false도 같은 조건이었는데 다르게 출력되었었습니다.)

#include <iostream>
#include <vector>
#include <queue>
#define MAX 402
#define SOURCE 0
#define SINK 1
#define INF 1e9
using namespace std;

int c[MAX][MAX], f[MAX][MAX];
vector<int> adj[MAX];
bool check[MAX];
int n, m;
int s, t;

void edmondsKarp(int source, int sink){
    while(true){
        int parent[MAX];
        fill(parent, parent + MAX, -1);
        queue<int> q;
        q.push(source);
        
        while(!q.empty()){
            int now = q.front();
            q.pop();
            
            for(int i = 0; i < adj[now].size(); i++){
                int next = adj[now][i];
                
                if(c[now][next] - f[now][next] > 0 && parent[next] == -1){
                    parent[next] = now;
                    q.push(next);
                }
            }
        }
        
        if(parent[sink] == -1) break;
        
        int temp = INF;
        
        for(int i = sink; i != source; i = parent[i]){
            temp = min(temp, c[parent[i]][i] - f[parent[i]][i]);
        }
        
        for(int i = sink; i != source; i = parent[i]){
            f[parent[i]][i] += temp;
            f[i][parent[i]] -= temp;
        }
    }
}

void bfs(int source){
    queue<int> q;
    q.push(source);
    check[source] = true;
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        
        for(int i = 0; i < adj[now].size(); i++){
            int next = adj[now][i];
            
            if(c[now][next] - f[now][next] > 0 && !check[next]){
                check[next] = true;
                q.push(next);
            }
        }
    }
}

int main(){
    cin >> n >> m;
    cin >> s >> t;
    
    // 정점 분할 in-out
    // in : i * 2, out : i * 2 + 1
    for(int i = 1, v; i <= n; i++){
        cin >> v;
        adj[i * 2].push_back(i * 2 + 1);
        adj[i * 2 + 1].push_back(i * 2);
        c[i * 2][i * 2 + 1] = v;
    }
    
    // edge 구성
    for(int i = 0; i < m; i++){
        int a, b; cin >> a >> b;
        // 1) a-out -> b-in
        adj[a * 2 + 1].push_back(b * 2);
        adj[b * 2].push_back(a * 2 + 1); // 역방향 연결은 해줘야 함, 아래 BFS와 이어짐
        c[a * 2 + 1][b * 2] = INF;
        // 2) b-out -> a-in
        adj[b * 2 + 1].push_back(a * 2);
        adj[a * 2].push_back(b * 2 + 1); // 역방향 연결은 해줘야 함
        c[b * 2 + 1][a * 2] = INF;
    }
    
    // SOURCE와 s-in, t-out과 SINK
    adj[SOURCE].push_back(s * 2);
    adj[s * 2].push_back(SOURCE);
    c[SOURCE][s * 2] = INF;
    c[s * 2][SOURCE] = INF;
    adj[t * 2 + 1].push_back(SINK);
    adj[SINK].push_back(t * 2 + 1);
    c[t * 2 + 1][SINK] = INF;
    c[SINK][t * 2 + 1] = INF;
    
    edmondsKarp(SOURCE, SINK);
    bfs(s * 2); // 그렇지 않으면 1210 질문에 있는 것처럼 2를 가지 못하게 되는 것으로 착각하여 버리게 됨
    
    for(int i = 1; i <= n; i++){
        if(check[i * 2] && !check[i * 2 + 1]){
            cout << i << ' ';
        }
    }
    
    /*
    for(int i = 1; i <= n; i++){
        cout << i << " Capacity " << c[i * 2][i * 2 + 1] << ' ';
        cout << i << " Flow " << f[i * 2][i * 2 + 1] << '\n';
    }
    */
    
    return 0;
}