최대 흐름 알고리즘 - 최고 레이 블 예비 흐름 추진 (HLPP)

어제 우 리 는 ISAP 알고리즘 을 배 웠 는데, 그것 은 증폭 로 알고리즘 의 큰 종류 에 속한다.오늘 배 운 알고리즘 은 프 리 플 로 우 추진 알고리즘 중 효율 적 인 유형 인 최고 레이 블 프 리 플 로 우 추진 (HLPP) 입 니 다.
프 리 플 로 우 추진
예 류 추진 은 매우 직관 적 인 네트워크 흐름 알고리즘 이다.만약 에 인터넷 흐름 에 손 으로 계산 하 라 고 하면 일반적인 생각 은 원점 에서 시작 해서 부족 한 것 을 만나면 빼 고 외환 점 까지 계속 밀어 내 는 것 이다.이것 이 바로 예 류 추진 알고리즘 의 기본 사상 이다.
각 노드 는 하나의 저수지 로 처음에 원점 에 무한 한 물이 있 었 다.처리 해 야 할 점 을 대기 열 로 유지 합 니 다.처음에 원점 을 넣 었 습 니 다. 모든 현재 점 에 대해 우 리 는 이 연못 에 있 는 유량 을 변 (수도관) 을 따라 인접 한 점 으로 미 룬 다음 에 인접 한 점 을 대열 에 넣 었 습 니 다.
알고리즘 사상 은 이와 같 지만 그 중 하 나 는 다음 과 같다. 이렇게 하면 두 가지 점 이 하나씩 밀 려 오고 하 나 는 밀 려 갈 수 있 고 결 과 는 순환 할 수 있다.이때 우 리 는 모든 점 에 하나의 높이 를 도입 하여 이 문 제 를 해결한다.
원점 의 높이 는 \ (n \) 이 고, 집합 점 의 높이 는 \ (0 \) 이 며, 다른 점 의 초기 높이 는 0 이다. 우 리 는 물 을 한 층 씩 내 려 가게 규정 한다. 즉, 우 리 는 \ (h [x] = h [v] + 1 \) 의 변 만 밀어 낸다.
한 점 에 물이 있 는데 도 내 놓 을 수 없다 면 주위 의 점 이 그 보다 높다 면 우 리 는 이 점 을 올 립 니 다. \ (h \) 값 이 연속 되 기 때문에 매번 이런 상황 이 발생 할 때마다 우 리 는 그것 에 하 나 를 더 합 니 다.만약 이 점 이 전혀 흘러 나 가지 않 는 다 면, 마지막 에 그것 은 \ (n + 1 \) 의 높이 로 올 라 가 원점 으로 되 돌아 갈 것 이다.
최고 레이 블
Tarjan 과 Goldberg 는 1986 년 에 일반 대기 열 을 우선 대기 열 로 바 꾸 고 매번 높이 가 가장 높 은 것 을 꺼 내 추진 하 는 최고 레이 블 예약 추진 알고리즘 을 제시 했다.Cheriyan 과 Maheshwari 는 1988 년 에 이렇게 하 는 복잡 도가 \ (O (n ^ 2 \ sqrt m) \ 라 는 것 을 증명 했다.
최적화 하 다.
즐겨 듣 는 gap 는 최적화 되 었 으 나 ISAP 와 는 형식 이 다르다.만약 에 우리 가 한 점 에 1 의 높이 를 올 렸 을 때 이 점 의 원래 높이 는 이미 점 이 없다 는 것 을 발견 하면 우 리 는 이 높이 보다 큰 점 을 모두 높이 로 설정 하고 그들 로 하여 금 원점 으로 돌아 가게 한다. 알고리즘 에 따라 그들 은 더 이상 물 을 송금 점 으로 미 룰 수 없 기 때문이다.(왜 다음 점 을 올 려 경 로 를 만 들 수 없 습 니까? 한 점 의 높이 는 모든 인접 점 의 높이 가 최소 치 에 하나 이기 때문에 이런 상황 이 발생 할 수 없습니다)
코드
여전히 poj 1273 모드 문제 지만 poj 는 오늘 끊 은 것 같 습 니 다. hdu 1532 는 같은 문제 입 니 다.
실측 에서 ISAP 가 빨리 달 리 는 것 은 ISAP 의 복잡 도 상계 가 매우 느슨 하고 HLPP 의 상계 가 매우 빡빡 해서 ISAP 가 무 작위 로 매우 빨리 달 리 는 것 으로 추정 된다.

#include
#include
#include
#include
#include
#include
using namespace std;
int read() {
    int x=0,f=1;
    char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}
const int maxn=1e3+10;
const int maxm=1e6+10;
const int inf=2147483646;
vector inv[maxn];
struct edge {
    int v,w,nxt;
} e[maxm<<1];
int h[maxn],tot,d[maxn],n,m,prs[maxn],gap[maxn];
bool able[maxn];
void add(int u,int v,int w) {
    e[++tot]=(edge){v,w,h[u]};
    h[u]=tot;
    e[++tot]=(edge){u,0,h[v]};
    h[v]=tot;
}
struct cmp {
    int x,h;
    cmp (int x=0,int h=0):x(x),h(h) {}
    inline bool operator < (const cmp &a) const {return h pq;
bool push(int x,int y,int p) {
    int w=min(prs[x],e[p].w);
    e[p].w-=w,e[p^1].w+=w,prs[x]-=w,prs[y]+=w;
    return w;
}
void Gap(int l,int s,int t) {
    for (int i=1;i<=n;++i) if (i!=s && i!=t && l

다음으로 전송:https://www.cnblogs.com/owenyu/p/6858123.html