KM 알고리즘 상세 설명

KM 알고리즘:
KM 는 대역 권 이분 도 를 구 하 는 데 가장 적합 한 알고리즘 이다.
원리:
우 리 는 2 분 그림 의 최 적 화 된 매 칭 을 요구 합 니 다. 직접 구 하면 구하 기 가 쉽 지 않 을 것 입 니 다. 모든 변 은 자신의 변 권 을 가지 고 있 기 때 문 입 니 다. 우 리 는 하나의 매 칭 을 요구 하여 모든 변 권 을 합 쳐 가장 큰 가 치 를 가 집 니 다.그 다음 에 지능 이 매우 높 은 KM 알고리즘 발명 자 는 이 문 제 를 띠 권 2 분 그림 의 완 비 된 일치 문 제 를 구 하 는 것 으로 바 꾸 었 다.
개념:

정상 표: 각 점 마다 하나의 정상 표 가 있 고 왼쪽 점 의 정상 표 지 는 lx [i] l x [i] 이 며 오른쪽 점 의 정상 표 지 는 ly [i] l y [i] 이다.

성질: 알고리즘 에 대한 임 의 시간 을 확보 하고 이 2 분 그림 에 속 하 는 임 의 한 변 e (u, v) e (u, v) 는 lx [u] + ly [v] ≥ w (u, v) l x [u] + l y [v] ≥ w (u, v) 가 있다.

실행 가능 한 변: u, v u, v 만족 lx [u] + ly [v] = w (u, v) l x [u] + l y [v] = w (u, v) 의 변

확대 로: 모두 실행 가능 한 변 으로 구성 되 고 헝가리 알고리즘 과 같이 하나의 일치 변, 하나의 일치 하지 않 는 변 으로 구성 되 며 두 단 은 모두 일치 하지 않 는 변 의 길이 다

.
방법:
모든 변 이 상기 성질 을 만족 시 키 는 이상 우 리 는 2 분 그림 에서 모든 가능 한 변 으로 구 성 된 완 비 된 매 칭 을 찾 을 수 있다 면 임의의 u, v u, v 가 lx [u] + ly [v] = w (u, v) l x [u] + l y [v] = w (u, v) 를 만족 시 킬 수 있다 면 우 리 는 이 완 비 된 매 칭 이 가장 좋 은 것 임 을 증명 할 수 있다 (정상 표 의 성질 참조).우리 가 이렇게 최 적 화 된 매 칭 을 구 할 수 있다 면 이런 정상 표 집합 을 만들어 위의 모든 조건 을 만족 시 켜 야 한다.처음에 우 리 는 모든 왼쪽 점 의 꼭 대 기 를 그것 과 연 결 된 가중치 의 가장 큰 변 의 가중치 로 설정 했다.그 다음 에 헝가리 알고리즘 으로 넓 은 길 을 한 번 씩 달 려 서 모두 실행 가능 한 변 으로 구 성 된 완 비 된 일치 가 될 때 까지 달 렸 다.그런데 데이터 가 준 그림 이 꼭 완벽 하 게 일치 하지 않 으 면 어 떡 하지?우 리 는 원 그림 에 없 는 변 권 치 를 0 으로 설정 할 수 있다.
맨 위 에 표 시 된 수정 사항:
분명히 이렇게 하면 반드시 조건 을 만족 시 키 는 완벽 한 매 칭 을 찾 을 수 있 는 것 은 아니다.그래서 우 리 는 성질 을 만족 시 키 는 상황 에서 점 의 정상 표 지 를 수정 하여 만족 조건 의 완 비 된 매 칭 을 찾 을 수 있 도록 해 야 한다.현재 교차 트 리 에 있 는 변 을 수정 하 는 것 을 고려 합 니 다. 왼쪽 에 있 는 점 의 정상 표 지 를 gap g a p 를 빼 면 해당 하 는 것 은 이미 일치 하 는 변 에 대해 오른쪽 에 있 는 대응 점 의 정상 표 지 는 gap g a p 를 더 해 야 원래 의 변 의 타당 성 이 변 하지 않 습 니 다.

양쪽 끝 이 교차 하 는 트 리 의 가장자리 (u, v) (u, v), lx [u] + ly [v] l x [u] + l y [v] 의 값 은 변화 가 없다.즉, 그것 은 원래 실행 가능 한 변 이 었 는데, 지금 은 여전히 실행 가능 한 변 이다.

양 끝 은 교차 트 리 의 가장자리 (u, v) (u, v), lx [u] 와 ly [v] l x [u] 와 l y [v] 모두 변화 가 없다.이 변 의 타당 성 은 변 하지 않 았 다 는 것 이다.

u 단 은 교차 트 리 에 있 지 않 습 니 다. v 단 은 교차 트 리 의 가장자리 (u, v) (u, v) 에 있 습 니 다. 그의 lx [u] + ly [v] l x [u] + l y [v] 의 값 이 증가 합 니 다.그것 은 원래 실행 가능 한 변이 아니 었 는데, 지금 은 여전히 실행 가능 한 변이 아니다

u 단 은 교차 트 리 에 있 고 v 단 은 교차 트 리 의 가장자리 (u, v) (u, v) 에 있 지 않 으 며 lx [u] + ly [v] l x [u] + l y [v] 의 값 이 감소 합 니 다.즉, 그것 은 원래 실행 가능 한 변이 아니 었 는데, 지금 은 실행 가능 한 변이 될 수 있다.

따라서 실행 가능 한 변 으로 구 성 된 확대 로 를 찾기 위해 우 리 는 가능 한 한 정상 표 지 를 수정 하여 실행 가능 한 변 의 조 수 를 증가 시 켜 야 한다. 위의 네 번 째 점 에 대응 하여 수 정 량 은 lx [u] + ly [v] - va [u] [v] l x [u] + l y [v] - v a [u] [v] 이다.전체 그림 이 제한 조건 을 만족 시 키 기 위해 수 정 량 은 u 단 이 교차 트 리 에 있 는 것 을 만족 시 키 는 것 이 고 v 단 은 교차 트 리 에 있 는 min (lx [u] + ly [v] - va [u]] min (l x [u] + l y [v] - v a [u] [v]) 이 아니다.
프로 세 스:
위의 수학 적 증명 과 분석 을 통 해 KM 알고리즘 의 절 차 를 얻 을 수 있 습 니 다.

헝가리 알고리즘 으로 모든 왼쪽 끝 점 에 넓 은 길 을 찾 아 준다.

확장 로 를 찾 지 못 하면 수 정 량 의 최소 치 를 기록 하고 방문 한 점 의 정상 표 지 를 수정 하 며 첫 번 째 단 계 를 반복 합 니 다

다음 지점 으로 옮 겨 증 광 로

시간 복잡 도:
인터넷 상에 서 많은 분석 이 엄밀 하지 않다. 우 리 는 위의 방법 에 따라 모든 점 에서 한 번 더 넓 은 길 을 찾 고 시간 적 으로 n n 을 찾 아야 한다. 매번 찾 을 때마다 n 개의 점 을 현재 의 실행 가능 한 변 에 추가 해 야 할 수도 있다. 시간 적 으로 또 하나의 n 을 찾 아야 한다. 매번 헝가리 에서 n2 n 2 개의 변 을 많이 방문 하기 때문에 시간 복잡 도 는 O (n4) O (n 4) 이다.
최적화:
우 리 는 이렇게 높 은 복잡 도 를 받 아들 일 수 없 기 때문에 최적화 해 야 한다.만약 에 정상 표 지 를 수정 한 후에 처음에 헝가리 를 달리 면 쓸데없는 순환 을 많이 낭비 할 수 있다 는 것 을 알 게 되 었 다. 현재 수정 한 후에 최소한 한 변 만 증가 할 수 있 기 때문에 우 리 는 수정 한 후에 정상 표 지 를 취 하 는 최소 수 정 량 이 있 는 그 점 만 다음 헝가리 를 진행 할 수 있다. 그러면 모든 확대 점 에 대해방문 한 총 변 수 는 기껏해야 n2 n 2 개 입 니 다.그러나 이렇게 하면 문제 가 있 을 수 있 습 니 다. 우 리 는 거 슬러 올 라 갈 때 일치 하 는 것 을 수정 할 수 없습니다. 여 기 는 하나의 링크 로 유지 하면 됩 니 다.

/*============================
 * Author : ylsoi
 * Problem : uoj80
 * Algorithm : KM
 * Time : 2018.6.16(updated)
 * =========================*/
#include
#include
#include
#include
#include
#include
using namespace std;
void File(){
    freopen("uoj80.in","r",stdin);
    freopen("uoj80.out","w",stdout);
}
template<typename T>bool chkmax(T &_,T __){return _<__ class="hljs-number">1) : 0;}
template<typename T>bool chkmin(T &_,T __){return _>__ ? (_=__,1) : 0;}
#define REP(i,a,b) for(register int i=a;i<=b;++i)
#define DREP(i,a,b) for(register int i=a;i>=b;--i)
#define MREP(i,x) for(register int i=beg[x];i;i=E[i].last)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define inf INT_MAX
const int maxn=400+10;
int nl,nr,m,n,dis[maxn][maxn],Ans[maxn];
int lw[maxn],rw[maxn],slack[maxn],be[maxn],fa[maxn];
bool vis[maxn];
ll ans;
bool Hungary(int las){
    vis[las]=1;//            
    int u=be[las];
    if(!u){
        while(las){
            be[las]=be[fa[las]];
            las=fa[las];
        }
        return true;
    }
    REP(i,1,n){
        int gap=lw[u]+rw[i]-dis[u][i];
        if(vis[i])continue;//             
        if(!gap){
            vis[i]=1;
            fa[i]=las;//                 ，     。
            if(Hungary(i))return true;
        }
        else if(chkmin(slack[i],gap))
            fa[i]=las;/*!!!  ，                        
               i                   i
                  gap       ，    chkmin       las  i   。*/
    }
    return false;
}
void KM(){
    REP(i,1,n){
        mem(fa);
        mem(vis);
        REP(j,1,n)slack[j]=inf;
        be[0]=i;
        int fr=0;
        while(1){
            if(Hungary(fr))break;
            int gap=inf;
            REP(j,1,n)if(!vis[j] && chkmin(gap,slack[j]))
                fr=j;
            REP(j,0,n)if(vis[j]){
                lw[be[j]]-=gap;
                if(j)rw[j]+=gap;
            }
            else slack[j]-=gap;
        }
    }
    REP(i,1,n)ans+=lw[i]+rw[i];
    printf("%lld
",ans);
    REP(i,1,n)if(dis[be[i]][i])Ans[be[i]]=i;
    REP(i,1,nl)printf("%d ",Ans[i]);
}
void init(){
    scanf("%d%d%d",&nl,&nr,&m);
    n=max(nl,nr);
    REP(i,1,m){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        dis[u][v]=w;
        chkmax(lw[u],w);
    }
}
int main(){
    File();
    init();
    KM();
    return 0;
}

많은 것 이 제 견해 입 니 다. 실 수 를 피 할 수 없습니다. 발견 이 있 으 면 지적 해 주 십시오. 감사합니다.