Network Flow Algorithm 3 - CyberFlower Algorithm

최대 유량을 구하는 네트워크 플로우 알고리즘인 Ford_Fulkerson 알고리즘과 Edmond Karp알고리즘을 소개해 드렸습니다. 네크워크 플로우 알고리즘 1

오늘은 동일한 역할을 하는 알고리즘이지만 시간복잡도가 더 좋은 Dinic 알고리즘을 소개하도록 하겠습니다.

Dinic의 전체적인 생김새는 F.F와 비슷합니다. 일단 대략적인 개관을 보도록 하겠습니다.

bfs를 이용하여 레벨 그래프를 만듭니다. capacity가 0 이하면 흐를 수 없음에 유의해 주어야 합니다.
만들어진 레벨 그래프를 기반으로 플로우를 흘려줍니다. 현재 노드에서 가장 마지막으로 방문한 점을 저장하는 배열을 하나 만들어 흘렸던 유량을 다시 확인하지 않도록 합니다.
1,2의 과정을 레벨 그래프를 만들 수 없을 때 까지(synk까지 연결이 되지 않을 때 까지) 반복합니다.

코드 세부 내용을 설명하자면, 기존의 일반적인 그래프 문제에는 그래프와 capacity를 아래 코드처럼 선언했었습니다.

vector<int> graph[SZ];
int cap[SZ][SZ];

하지만 네트워크 플로우 알고리즘에서는 정점의 개수가 $ 10^4 $ 이상인 경우도 충분히 존재할 수 있습니다. 따라서 저는 Edge라는 구조체를 하나 선언하여 간선과 capacity에 대한 정보를 저장하도록 하겠습니다.

Dinic 알고리즘을 이용한 열혈강호 2 문제의 코드입니다.

#include<bits/stdc++.h>
#define pb push_back
#define INF (int)1e9
using namespace std;
struct edge{
	int to,cap,rev;
	edge(int to, int cap, int rev){
		this->to=to;		// 어디로 흐르는가
		this->cap=cap;
		this->rev=rev;	// 역간선이 저장되어 있는 index number 저장
	}
};
struct Dinic{
	int n,m,src,dst;
	vector<vector<edge>> graph;
	vector<int> crt;
	vector<int> lv;
	Dinic(int n, int m, int src, int dst){
		this->n=n;
		this->m=m;
		this->src=src;
		this->dst=dst;
		graph.resize(n+m+5);
		crt.resize(n+m+5);
		lv.resize(n+m+5);
	}
	void push_edge(int a, int b, int capa){
		graph[a].pb(edge(b,capa,graph[b].size()));
		graph[b].pb(edge(a,0,graph[a].size()-1));
	}
	bool bfs(){
		for(int i=0;i<=n+m+1;i++) lv[i]=0;
		queue<int> q;
		q.push(src); lv[src]=1;
		while(!q.empty()){
			int f=q.front(); q.pop();
			for(auto nxt:graph[f]){
				if(lv[nxt.to] || nxt.cap<=0) continue;
				q.push(nxt.to); lv[nxt.to]=lv[f]+1;
			}
		}
		return lv[dst]!=0;
	}
	int dfs(int x, int mnc){
		if(x==dst) return mnc;
		for(int &i=crt[x];i<(int)graph[x].size();i++){
			auto &e=graph[x][i];
			if(lv[x]>=lv[e.to] || e.cap<=0) continue;
			int f=dfs(e.to,min(mnc,e.cap));
			if(f>0){
				e.cap-=f;
				graph[e.to][e.rev].cap+=f;
				return f;
			}
		}
		return 0;
	}
	int flow(){
		int ans=0;
		while(bfs()){
			for(int i=0;i<=n+m+1;i++) crt[i]=0;
			int f;
			while((f=dfs(src,INF)) > 0) {
				ans+=f;
			}
		}
		return ans;
	}
};
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n,m; cin>>n>>m;
	Dinic dn=Dinic(n,m,0,n+m+1);
	for(int i=1;i<=n;i++) dn.push_edge(dn.src,i,2);
	for(int i=n+1;i<=n+m;i++) dn.push_edge(i,dn.dst,1);
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		for(int j=0;j<x;j++){
			int y; cin>>y;
			dn.push_edge(i,n+y,1);
		}
	}
	cout<<dn.flow();
	return 0;
}

Dinic Algorithm