BOJ 18653 Honeycomb

문제 링크입니다.

문제 요약

주어진 벌집 모양 그래프의 모든 두 정점 쌍 $(s,t)$에 대한 최소 컷의 합을 구하세요.

풀이

MFMC 정리가 있으니 모든 정점 쌍에 대한 최대 유량의 합을 구하면 됩니다. 아무래도 ${\cal O}(N^2)$ 번 플로우를 구하기에는 시간이 모자랍니다.

Gomory-Hu Tree라는 자료 구조가 있습니다. 주어진 그래프를 트리의 형태로 압축해, 모든 정점 쌍이 원래의 그래프와 같은 최대 유량 = 경로 상의 간선 가중치 중 최솟값을 갖도록 합니다. 만드는 과정에서 트리의 간선으로 표현되는 ${\cal O}(N)$ 개 쌍에 대해서만 플로우를 돌리기 때문에 문제를 해결하기에 충분합니다.

트리의 구축 방법을 간단히 설명하자면,

1. 그래프의 정점에 편의 상 $1$부터 $N$까지 번호를 매기겠습니다.
2. $2$번부터 $N$번까지의 모든 정점의 부모를 $1$번 정점으로 설정합니다.
3. $2$번 정점부터 $N$번 정점까지 순서대로 다음의 과정을 반복합니다. 이번 정점을 $i$번이라고 하면,
   1. $i$번 정점과 그 부모 정점 사이의 최소 컷을 구합니다. 이에 따라 그래프는 부모 정점을 포함하는 연결 요소 $P$와 $i$번 정점을 포함하는 연결 요소 $S$로 나뉩니다.
   2. $S$에 포함되는 정점 중 $i$보다 번호가 큰 정점의 부모를 $i$번 정점으로 설정합니다.

이게 끝입니다! 시간 복잡도는 ${\cal O}(N)$번 돌아가는 플로우 알고리즘이 지배적으로 작용합니다. 이 문제에서는 디닉을 사용하는 경우 모든 간선의 가중치가 1로 동일하므로 총 ${\cal O}(N^2 \sqrt N)$의 시간 복잡도에 동작합니다.

Gomory-Hu Tree를 구한 뒤 가중치가 큰 간선부터 Union-Find 등으로 합쳐주면 문제를 해결할 수 있습니다.

그래프 특성 상 정점이 많고 간선이 적습니다. 그래프를 인접 행렬 대신 간선 리스트로 구현해야 안정적으로 AC를 받을 수 있을 거에요.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 998244353;

struct GomoryHu{
	struct Edge{int to, cap, rev, orig;};
	int N, source, sink;
	vector<vector<Edge>> e;
	vector<int> lv, vis, par;
	vector<array<int,3>> E;
	GomoryHu(){N=0;}
	void resize(int n){
		N = n;
		e.assign(N+1, {});
		lv.resize(N+1);
		vis.resize(N+1);
		par.resize(N+1);
		E.clear();
	}
	void addEdge(int u, int v){
		e[u].push_back({v, 1, (int)e[v].size(), 1});
		e[v].push_back({u, 1, (int)e[u].size()-1, 1});
	}
	bool getLevel(){
		fill(lv.begin(), lv.end(), -1);
		queue<int> q; lv[source] = 0; q.push(source);
		while(q.size()){
			int now = q.front();q.pop();
			for(auto& [nxt, w, rev, orig] : e[now]) if(w > 0 && lv[nxt] == -1){
				lv[nxt] = lv[now]+1;
				q.push(nxt);
			}
		}
		return lv[sink] != -1;
	}
	int getFlow(int now, int f){
		if(now == sink) return f;
		for(int& i = vis[now]; i < e[now].size(); i++){
			auto& [nxt, w, rev, orig] = e[now][i];
			if(w > 0 && lv[nxt] == lv[now]+1){
				int nf = getFlow(nxt, min(f, w));
				if(nf){
					w -= nf;
					e[nxt][rev].cap += nf;
					return nf;
				}
			}
		}
		return 0;
	}
	int dinic(){
		for(int i = 1; i <= N; i++) for(auto& [nxt, w, rev, orig] : e[i]) w = orig;
		int ret = 0;
		while(getLevel()){
			fill(vis.begin(), vis.end(), 0);
			while(1){
				int f = getFlow(source, INF);
				if(!f) break;
				ret += f;
			}
		}
		return ret;
	}
	void getTeam(int now){
		vis[now] = 1; if(source < now && par[now] == par[source]) par[now] = source;
		for(auto& [nxt, w, rev, orig] : e[now]) if(w > 0 && !vis[nxt]) getTeam(nxt);
	}
	void build(){
		for(int i = 1; i <= N; i++){
			if(par[i] == i) continue;
			source = i; sink = par[i]; int F = dinic();
			E.push_back({F, par[i], i});
			fill(vis.begin(), vis.end(), 0);
			getTeam(source);
		}
		sort(E.begin(), E.end(), greater<>());
	}
} GH;


int n, m;
char a[432][642];
int idx[432][642];
int par[3030];

int f(int x){
	return par[x] < 0 ? x : par[x] = f(par[x]);
}

void u(int x, int y){
	x = f(x); y = f(y);
	if(x == y) return;
	if(x > y) swap(x, y);
	par[x] += par[y]; par[y] = x;
}

void input(){
	cin >> n >> m; cin.ignore(); string s; int IDX = 0;
	vector<pii> p; 
	for(int i = 1; i <= 4*n+3; i++){
		getline(cin, s);
		for(int j = 0; j < s.size(); j++){
			a[i][j+1] = s[j]; if(a[i][j+1] == '*') idx[i][j+1] = ++IDX, p.emplace_back(i, j+1);
			else idx[i][j+1] = 0;
		}
	}
	GH.resize(IDX); memset(par, -1, sizeof(par));
	for(auto& [y, x] : p){
		if(a[y+1][x-3] != '\\' && idx[y+2][x-6]){
			GH.addEdge(idx[y][x], idx[y+2][x-6]); u(idx[y][x], idx[y+2][x-6]);
		}
		if(a[y+2][x] != '-' && idx[y+4][x]){
			GH.addEdge(idx[y][x], idx[y+4][x]); u(idx[y][x], idx[y+4][x]);
		}
		if(a[y+1][x+3] != '/' && idx[y+2][x+6]){
			GH.addEdge(idx[y][x], idx[y+2][x+6]); u(idx[y][x], idx[y+2][x+6]);
		}
	}
	for(int i = 1; i <= IDX; i++) GH.par[i] = f(i);
}

void solve(){
	input(); GH.build(); memset(par, -1, sizeof(par)); ll ans = 0;
	for(auto& [F, x, y] : GH.E){
		ans += (ll)F*par[f(x)]*par[f(y)]; u(x, y);
	}
	cout << ans << '\n';
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int T; cin >> T; for(int tc = 1; tc <= T; tc++){
		cout << "Case #" << tc << ": "; solve();
	}
}