KM 알고리즘 상세 설명
KM 는 대역 권 이분 도 를 구 하 는 데 가장 적합 한 알고리즘 이다.
원리:
우 리 는 2 분 그림 의 최 적 화 된 매 칭 을 요구 합 니 다. 직접 구 하면 구하 기 가 쉽 지 않 을 것 입 니 다. 모든 변 은 자신의 변 권 을 가지 고 있 기 때 문 입 니 다. 우 리 는 하나의 매 칭 을 요구 하여 모든 변 권 을 합 쳐 가장 큰 가 치 를 가 집 니 다.그 다음 에 지능 이 매우 높 은 KM 알고리즘 발명 자 는 이 문 제 를 띠 권 2 분 그림 의 완 비 된 일치 문 제 를 구 하 는 것 으로 바 꾸 었 다.
개념:
방법:
모든 변 이 상기 성질 을 만족 시 키 는 이상 우 리 는 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 를 더 해 야 원래 의 변 의 타당 성 이 변 하지 않 습 니 다.
따라서 실행 가능 한 변 으로 구 성 된 확대 로 를 찾기 위해 우 리 는 가능 한 한 정상 표 지 를 수정 하여 실행 가능 한 변 의 조 수 를 증가 시 켜 야 한다. 위의 네 번 째 점 에 대응 하여 수 정 량 은 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;
}
많은 것 이 제 견해 입 니 다. 실 수 를 피 할 수 없습니다. 발견 이 있 으 면 지적 해 주 십시오. 감사합니다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
2016 장락캠프 Day 7법칙을 찾아 한 발 + 트리 그룹 한 발 O (nlog^2n) 그림을 그려 보면 두 경로가 서로 교차하면 반드시 LCA와 관련이 있고, 두 개의 매거진 충돌 노선이 있고, 가장자리를 만들어 최대 독립 서브집합을 만들...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.