백준 22990번: 사이클 (C++)

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

22990번: 사이클

---

Solved By: Network Flow, Bipartite Matching, MCMF

 

단순 사이클이란 시작점과 끝점을 제외한 중복 점이 없는 사이클입니다.

이러한 부분에서 노드를 정점 분할로 두고 생각해야겠다 했지만, '모든 정점을 사용했는가'는 알아낼 수 있는 방법이 떠오르지 않았습니다. 또한, 모든 정점을 사용해야 하지만 모든 정점이 한 사이클에 포함되었는지, 몇 개의 정점이 나뉘어서 단순 사이클을 형성했는지도 알 방법이 없었습니다.

 

Reference(https://justicehui.github.io/ps/2021/09/22/BOJ22990/)

 

해당 글에서 사이클의 특징을 알 수 있었습니다. 노드가 3인 그래프가 1->3, 3->2, 2->1의 형태로 사이클 형성하고 있다면

	1	2	3
1			O
2	O
3		O

위 표와 같은 형태로 나타낼 수 있습니다. 위 표에서 알 수 있는 것은 한 행(한 노드)에는 무조건 하나씩 매칭 되는 열이 있으며 이는 서로 다 다릅니다. 즉, 사이클은 노드끼리 이분매칭 시켰을 때, 노드 개수만큼 유량이 흐른다면 사이클이 형성되었다고 볼 수 있습니다.

 

그렇다면 이 문제를 이분 매칭이자 MCMF문제로 바꾸어 볼 수 있습니다. 유량 함수를 짤 때, 이분 매칭과 MCMF를 동시에 구하여 리턴하도록 합시다.

 

Flow값이 노드의 개수가 아니라면 단순 사이클이 아니라는 뜻으로 0을 출력하고 종료시키고, 개수가 맞다면 1을 출력 후, 최소 비용값을 출력해줍니다.

 

이분 매칭을 하기 위해서는 Node를 Node * 2 = in, Node * 2 + 1 = out으로 정점 분할을 해주었습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define MAX 404
#define INF 0x3f3f3f3f3f3f3f3f
#define SOURCE 402
#define SINK 403
#define ll long long
using namespace std;

vector<int> adj[MAX];
int N, M;
ll c[MAX][MAX], f[MAX][MAX];
ll cost[MAX][MAX];
ll W[MAX][MAX];

void addLine(int a, int b, ll cap, ll co){
    adj[a].push_back(b);
    adj[b].push_back(a);
    c[a][b] = cap;
    cost[a][b] = co;
    cost[b][a] = -co;
}

pair<ll, ll> flow_cost(int source, int sink){
    ll Flow = 0, Cost = 0;
    while(true){
        int parent[MAX];
        bool isinQ[MAX];
        ll dist[MAX];
        queue<int> q;
        
        fill(parent, parent + MAX, -1);
        fill(dist, dist + MAX, INF);
        
        q.push(source);
        dist[source] = 0;
        isinQ[source] = true;
        
        while(!q.empty()){
            int now = q.front();
            q.pop(); isinQ[now] = false;
            
            for(int i = 0; i < adj[now].size(); i++){
                int next = adj[now][i];
                
                if(c[now][next] - f[now][next] > 0
                && dist[now] + cost[now][next] < dist[next]){
                    dist[next] = dist[now] + cost[now][next];
                    parent[next] = now;
                    
                    if(!isinQ[next]){
                        isinQ[next] = true;
                        q.push(next);
                    }
                }
            }
        }
        
        if(parent[sink] == -1) break;
        
        ll temp = INF;
        
        for(int i = sink; i != source; i = parent[i]){
            if(c[parent[i]][i] - f[parent[i]][i] < temp){
                temp = c[parent[i]][i] - f[parent[i]][i];
            }
        }
        
        Flow += temp;
        for(int i = sink; i != source; i = parent[i]){
            Cost += temp * cost[parent[i]][i];
            
            f[parent[i]][i] += temp;
            f[i][parent[i]] -= temp;
        }
    }
    
    return {Flow, Cost};
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N >> M;
    memset(W, 0x3f3f, sizeof(W));
    for(int i = 1; i <= M; i++){
        int v, u; ll w; cin >> v >> u >> w;
        if(W[v][u] > w){
            W[v][u] = w;
        }
    }
    
    for(int i = 1; i <= N; i++){
        addLine(SOURCE, i * 2, 1, 0);
        addLine(i * 2 + 1, SINK, 1, 0);
        for(int j = 1; j <= N; j++){
            if(W[i][j] != 0x3f3f) addLine(i * 2, j * 2 + 1, 1, W[i][j]);
        }
    }
    
    auto res = flow_cost(SOURCE, SINK);
    
    if(res.first != N){
        cout << 0; return 0;
    }
    else cout << 1 << '\n' << res.second << '\n';
    
    for(int i = 2; i <= 2 * N; i += 2){
        for(auto j : adj[i]){
            if(f[i][j] == 1){
                cout << i / 2 << ' ' << j / 2 << '\n';
            }
        }
    }
    
    return 0;
}