백준 14955번: How Many to Be Happy? (C++)

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

14955번: How Many to Be Happy?

---

Solved By: MST, MFMC

 

Undirected Graph에서 우선 MST를 구합니다. -> Kruskal 사용

그다음 edge를 처음부터 하나씩 탐색해줍니다. 그 과정에서 각 edge당 H(e)의 값을 구할 겁니다.

 

Solution: edge의 H(e)를 구하는 과정

 

1)

edge가 MST에 속한 경우입니다.

MST를 만드는 과정에서 체크해둔 set을 통해 set에 edge가 존재한다면 H(e)를 0으로 알고, continue 시켜주었습니다.

int source = edges[i].first.first;
int sink = edges[i].first.second;
// MST에 존재하는 edge일 때
// H(e) = 0
if(st.count({source, sink})) continue;

2)

edge가 MST에 속하지 않은 경우입니다.

이 edge를 MST에 속하게 만들어야 합니다.

MST의 특성에 따라서 두 노드 사이에 연결하는 edge(path)의 가중치가 가장 작아야 합니다.

 

즉, node S, E가 있다고 가정했을 때, 두 노드를 잇는 path(edge의 개수가 1개이거나 2개 이상)는 여러 개 존재할 것입니다. 탐색 중인 edge가 MST의 조건에 만족하도록 탐색 중인 edge보다 낮은 가중치를 가지며 S와 E사이에 path로 존재하는 edge들이 없어져야 합니다.

 

왜냐하면 S와 E를 잇는 path 중 탐색 중인 edge보다 작은 가중치를 가지는 path가 있을 경우 그 path가 MST에 속해지기 때문입니다.

=> 주어진 edge를 제외한 가중치가 작은 edge들을 모아 만들어진 path 중 S로부터 E로 가는 path의 개수를 구해야 합니다.

edge의 총 개수가 아닌 path의 개수를 구하는 것과 같습니다. (path에서 하나의 edge라도 끊어지면 그 path는 망가지기 때문)

 

탐색 중인 edge보다 작은 가중치를 가진 edge들을 모아 adjust list를 만들고, S를 Source, E를 Sink, Undirected Graph이기 때문에 양방향으로 edge의 capacity를 1로 둔 상태에서 MFMC를 구하면 끊어야 하는 edge의 최소 개수를 구할 수 있습니다.

 

2번의 경우를 코드로 나타낸 것이 아래 코드입니다.

MST 구하는 과정에서 간선의 가중치 오름차순에 따라 정렬이 되어있기 때문에 for문을 저렇게 작성해주었습니다.

int weight = edges[i].second;
        
// MST가 아닌 간선이 간선으로 이어지게 하려면
// 현재 간선의 가중치보다 작은 간선들을 없애면서
// 현재 간선을 이어야 한다.
for(int j = 0; j < i; j++){
    int s = edges[j].first.first;
    int e = edges[j].first.second;
    adj[s].push_back(e);
    adj[e].push_back(s);
    c[s][e] = 1; c[e][s] = 1;
}
        
result += edmondsKarp(source, sink);

하지만, 이대로 끝난다면 틀립니다. 같은 가중치를 가지는 간선을 생각해주어야 합니다.

그래서 for문의 조건에 다음이 더 추가됩니다.

int weight = edges[i].second;
        
// MST가 아닌 간선이 간선으로 이어지게 하려면
// 현재 간선의 가중치보다 작은 간선들을 없애면서
// 현재 간선을 이어야 한다.
for(int j = 0; j < i && edges[j].second < weight; j++){
    int s = edges[j].first.first;
    int e = edges[j].first.second;
    adj[s].push_back(e);
    adj[e].push_back(s);
    c[s][e] = 1; c[e][s] = 1;
}
        
result += edmondsKarp(source, sink);

그리고, 매번 edge마다 Max Flow를 구하기 때문에 flow배열을 초기화시키는 것을 잊지 말아야 합니다.

 

+) 처음으로 풀었던 다이아 문제가 플레 1로 내려가고, 다시 처음으로 풀어본 다이아 문제네요.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#define MAX 101
#define LOG_MAX 7
#define INF 1e9
#define pii pair<int, int>
using namespace std;

vector<pair<pii, int>> edges;
vector<int> adj[MAX];
int n, m;
int uf[MAX];
int c[MAX][MAX], f[MAX][MAX];
set<pii> st;

bool cmp(pair<pii, int> a, pair<pii, int> b){
    return a.second < b.second;
}

int getRoot(int node){
    if(node == uf[node]) return node;
    else return uf[node] = getRoot(uf[node]);
}

bool find(int a, int b){
    int ga = getRoot(a);
    int gb = getRoot(b);
    
    if(ga != gb) return true;
    else return false;
}

void unionNodes(int a, int b){
    int ga = getRoot(a);
    int gb = getRoot(b);
    
    if(ga < gb) uf[gb] = ga;
    else uf[ga] = gb;
}

int edmondsKarp(int source, int sink){
    int maxFlow = 0;
    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;
        }
        
        maxFlow += temp;
    }
    return maxFlow;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int a, b, w; cin >> a >> b >> w;
        // MST input
        edges.push_back({{a, b}, w});
    }
    
    sort(edges.begin(), edges.end(), cmp);
    for(int i = 1; i <= n; i++) uf[i] = i;
    
    // Kruskal
    for(int i = 0; i < edges.size(); i++){
        int first = edges[i].first.first;
        int second = edges[i].first.second;
        if(find(first, second)){
            unionNodes(first, second);
            st.insert({first, second});
        }
    }
    
    int result = 0;
    for(int i = 0; i < edges.size(); i++){
        int source = edges[i].first.first;
        int sink = edges[i].first.second;
        // MST에 존재하는 edge일 때
        // H(e) = 0
        if(st.count({source, sink})) continue;
        
        // adj init
        for(int j = 1; j <= n; j++) adj[j].clear();
        
        int weight = edges[i].second;
        
        // MST가 아닌 간선이 간선으로 이어지게 하려면
        // 현재 간선의 가중치보다 작은 간선들을 없애면서
        // 현재 간선을 이어야 한다.
        for(int j = 0; j < i && edges[j].second < weight; j++){
            int s = edges[j].first.first;
            int e = edges[j].first.second;
            adj[s].push_back(e);
            adj[e].push_back(s);
            c[s][e] = 1; c[e][s] = 1;
        }
        
        result += edmondsKarp(source, sink);
        
        for(int u = 1; u <= n; u++){
            for(int v = 1; v <= n; v++){
                f[u][v] = 0;
            }
        }
    }
    
    cout << result;
    return 0;
}