가중 일반 매칭 – 학습

1강 가중치 블로섬: 일반 그래프 최적 매칭 공식

문제

일반(비이분) 그래프에서 간선 가중치 합이 최대 인 매칭을 찾는다. 이분 그래프라면 헝가리안/min-cost-flow로 풀리지만, 일반 그래프에는 홀수 사이클(블로섬) 때문에 그것들이 통하지 않는다. 가중치 블로섬(Edmonds' weighted blossom) 알고리즘이 정답이다.

비가중 블로섬이 "증가 경로 + 블로섬 수축"이었다면, 가중치 버전은 거기에 LP 쌍대(이중 변수) 를 얹는다.

LP와 쌍대

최대 가중치 매칭의 LP 완화는 다음과 같다(변수 $x_e \ge 0$ ):

$\max \sum_e w_e x_e \quad\text{s.t.}\quad \sum_{e \ni v} x_e \le 1\ (\forall v),\quad \sum_{e \subseteq B} x_e \le \tfrac{|B|-1}{2}\ (\forall \text{홀수집합 }B).$

마지막 홀수 집합(blossom) 제약 이 일반 그래프 매칭 다면체의 핵심(Edmonds의 정리)이다. 그 쌍대 변수:

$$y_v$$ : 정점 잠재값(potential).
$z_B \ge 0$ : 홀수 집합 $$B$$ 의 잠재값.

상보 여유(complementary slackness)

최적성의 조건은 모든 간선 $$e = (u, v)$$ 에 대해

$\text{slack}(e) = y_u + y_v + \sum_{B \ni e} z_B - w_e \ge 0,$

이고, 매칭 간선은 slack이 정확히 0(타이트)이어야 한다. 또 $$z_B > 0$$ 인 블로섬은 "완전히 매칭"되어 있어야 한다. 알고리즘은 이 조건을 유지하며 잠재값을 조정해 점점 더 큰 타이트 매칭을 만든다.

알고리즘 골격 (primal-dual)

잠재값 초기화: $y_v = \max_e w_e / 2$ 등, 모든 slack $\ge 0$ .
노출 정점에서 교대 숲 을 자란다(비가중 블로섬과 동일한 even/odd 라벨).
slack 0인 간선만 "사용 가능". 사용 가능한 간선이 부족하면 잠재값 조정(dual update):
- even 정점의 $$y$$ 를 $\delta$ 줄이고, odd 정점의 $$y$$ 를 $\delta$ 늘린다.
- 블로섬 $$z_B$$ 도 그에 맞춰 조정.
- $\delta$ 는 "다음 사건"(새 타이트 간선, 블로섬 형성/해체)이 일어나는 최소값.
타이트 간선으로 증가 경로가 생기면 매칭 확장. 블로섬은 수축; $$z_B = 0$$ 이 되면 확장(expand).
더 이상 개선 불가하면 종료 → 최적.

네 가지 $\delta$ 사건

잠재값 조정 시 다음 중 최소를 $\delta$ 로 잡는다.

사건	조건
$\delta_1$	even 정점 $y_v \to 0$ (최대 가중치 매칭에서 정점 노출 허용 시)
$\delta_2$	even–free 간선 타이트
$\delta_3$	even–even 간선 타이트 (블로섬/증가 후보)
$\delta_4$	odd 블로섬의 $z_B \to 0$ (확장 시점)

이 사건 구동(event-driven) 방식이 복잡도를 낮춘다.

복잡도

표준 구현은 $$O(V^3)$$ . 더 정교한 구현(우선순위 큐로 $\delta$ 관리)은 $O(VE \log V)$ 또는 $$O(V^3)$$ 상수 개선. $V \le 500$ 급에서 안정.

다음 강의에서 구현 구조와 사건 처리 디테일을 본다.

2강 가중 블로섬 구현 구조 공식

전체 설계

가중 블로섬은 코드가 길다. 핵심 자료구조와 사건 루프를 모듈로 정리한다. (1-indexed, 최대 가중치 완전/일반 매칭 둘 다 지원하도록.)

const int INF = 1e9;
int n, m;                         // 정점 수, 블로섬 포함 노드 수
int g[N][N];                      // 간선 가중치(없으면 0/음수)
int lab[N];                       // y_v 잠재값(블로섬엔 z_B/2 인코딩)
int match_[N], slack_[N], st[N];  // 매칭, slack 최소 간선, 소속 블로섬
int par[N], flower_from[N][N];    // 교대 트리 부모, 블로섬 진입 정점
vector<int> flower[N];            // 각 블로섬의 자식 노드 순환열
int S[N], vis[N];                 // even=0/odd=1 라벨, 방문
queue<int> q;

slack과 사건 값

int eDelta(int u, int v){          // 간선 (u,v)의 절반-slack
    return lab[u] + lab[v] - g[u][v]*2;   // 가중치 2배 스케일 관례
}

가중치를 2배로 스케일해 정수 연산을 유지하는 것이 표준 트릭(절반값 회피).

교대 트리 확장(BFS)

void setSlack(int x){
    slack_[x]=0;
    for(int u=1;u<=n;u++)
        if(g[u][x]>0 && st[u]!=x && S[st[u]]==0)
            if(!slack_[x] || eDelta(u,x)<eDelta(slack_[x],x))
                slack_[x]=u;
}
void push(int x){ if(x<=n) q.push(x); else for(int t:flower[x]) push(t); }
void setSt(int x,int b){ st[x]=b; if(x>n) for(int t:flower[x]) setSt(t,b); }

블로섬 형성(addBlossom)과 확장(expandBlossom)

// even-even 간선 (u,v)가 같은 트리 → 공통 조상 b를 베이스로 블로섬 생성
void addBlossom(int u, int lca, int v){
    int b = n+1; while(b<=m && st[b]) b++;
    if(b>m) m=b;
    lab[b]=0; S[b]=0;
    match_[b]=match_[lca];
    flower[b].clear(); flower[b].push_back(lca);
    // u쪽·v쪽 둘레를 따라 lca까지 flower[b] 채우기 ...
    setSt(b,b);
    // 블로섬 내부 even/odd 재라벨 및 큐 삽입 ...
}
void expandBlossom(int b){
    // z_b == 0 인 블로섬을 풀어 둘레를 다시 트리에 편입 ...
}

(둘레 추적은 flower_from/par로 양방향을 따라가며 채운다. 비가중 블로섬의 markPath와 유사하되 라벨/매칭 보존이 추가됨.)

잠재값 조정(dual update) — 핵심 사건 루프

bool augment(){                    // 한 번의 증강 시도
    fill(S+1,S+m+1,-1); fill(slack_+1,slack_+m+1,0);
    q={};
    for(int x=1;x<=m;x++) if(st[x]==x && !match_[x]){ par[x]=0; S[x]=0; push(x); }
    if(q.empty()) return false;
    while(true){
        while(!q.empty()){
            int u=q.front(); q.pop();
            for(int v=1;v<=n;v++) if(g[u][v]>0 && st[u]!=st[v]){
                if(eDelta(u,v)==0){            // 타이트 간선
                    // free면 증가, even-even이면 블로섬, 아니면 트리 확장
                } else if(S[st[v]]==0)
                    setSlack(st[v]);
            }
        }
        // δ = min(δ1, δ2, δ3, δ4) 계산
        int d=INF;
        for(int b=n+1;b<=m;b++) if(st[b]==b && S[b]==1) d=min(d, lab[b]/2);  // δ4
        for(int x=1;x<=n;x++) if(st[x]==x && slack_[x]){
            int dd=eDelta(slack_[x],x);
            if(S[st[x]]==-1) d=min(d, dd);       // δ2
            else if(S[st[x]]==0) d=min(d, dd/2); // δ3
        }
        // 잠재값 적용
        for(int u=1;u<=n;u++){
            if(S[st[u]]==0) lab[u]-=d;
            else if(S[st[u]]==1) lab[u]+=d;
        }
        for(int b=n+1;b<=m;b++) if(st[b]==b){
            if(S[b]==0) lab[b]+=d*2;
            else if(S[b]==1) lab[b]-=d*2;
        }
        // δ에 해당하는 사건 처리(타이트 간선 재검사 / 블로섬 확장)
        // 증가 경로 완성 시 return true;
    }
}

(증가/블로섬/확장 디테일은 위 골격의 주석 자리에 채운다. 전체 길이상 본 강의는 구조 에 집중한다.)

메인

long long solve(){
    int wmax=0; for(int u=1;u<=n;u++) for(int v=1;v<=n;v++) wmax=max(wmax,g[u][v]);
    for(int u=1;u<=n;u++){ st[u]=u; lab[u]=wmax; }   // 초기 잠재값
    while(augment()) {}
    long long tot=0;
    for(int u=1;u<=n;u++) if(match_[u]>u) tot+=g[u][match_[u]];
    return tot;
}

함정과 검증

가중치 2배 스케일 을 일관되게(절반값/홀수 회피).
블로섬 둘레 추적의 방향성·라벨 보존이 가장 버그가 잦은 부분.
검증: 이분 그래프에 넣으면 헝가리안과 동일 답이어야 함. $$K_4$$ 등 작은 비이분 그래프 손계산.
초기 잠재값을 충분히 크게 잡아 모든 slack $\ge 0$ 유지.

복잡도 $$O(V^3)$$ . $V \le 400 \sim 500$ 급 일반 그래프 최대 가중치 매칭에 쓴다. 실전에선 검증된 라이브러리 구현을 베이스로 두는 것을 권한다.