비용 흐름 템 플 릿 - ZKW

우선 SPFA 알고리즘 을 살 펴 보 자.
d [x] = x 에서 T 까지 의 최 단 거 리 를 설정 합 니 다.
i 에 대해 j 는 반드시 d [j] + c [i] [j] > = d [i] 가 있어 야 한다.
SPFA 알고리즘 은 d [j] + c [i] [j] = d [i] 의 등식 을 찾 을 때마다 가장 짧 은 길 로 답 을 업데이트 하 는 것 입 니 다.이렇게 되면 이미 구 한 것 을 충분히 이용 하지 못 하고 어떤 그림 들 은 매우 느 릴 것 이다.
우 리 는 KM 알고리즘 의 사상 을 참고 하여 매번 d [i] 를 조금 만 확대 하면 범위 가 더 큰 j 를 찾 을 수 있 고 답 도 맞다.매번 높 아 지 는 거 리 는 이미 지나 간 점 의 최소 높이 차이 로 sap 와 유사 하 다.
기본:

int n, S, T, ans1, ans2; // ans1      ， ans2      。 
int tot = 1, final[Maxn], dis[Maxn], bz[Maxn]; // dis   T   。 
struct edge {
    int to, next, r, w;
}a[Maxm];

void link(int x,int y,int r,int w) {
    a[++tot].next = final[x], a[tot].to = y, a[tot].r = r, a[tot].w = w, final[x] = tot;
    a[++tot].next = final[y], a[tot].to = x, a[tot].r = 0, a[tot].w = -w, final[y] = tot;
} //     

ZKW：

int aug(int x,int flow) {
    if(x == T) {
        ans1 += flow;
        ans2 += dis[S] * flow;
        return flow;
    }
    bz[x] = 1;
    int use = 0;
    for(int i = final[x]; i; i = a[i].next) {
        int y = a[i].to;
        if(!bz[y] && a[i].r && dis[y] + a[i].w == dis[x]) {
            int tmp = aug(y, min(a[i].r, flow - use));
            a[i].r -= tmp; a[i ^ 1].r += tmp; use += tmp;
            if(use == flow) return use;
        }
    }
    return use;
}

bool change() {
    int minh = INF;
    fo(i, 1, T) if(bz[i])
        for(int k = final[i]; k; k = a[k].next)
            if(a[k].r && !bz[a[k].to])
                minh=min(minh, dis[a[k].to] + a[k].w - dis[i]);
    if(minh == INF) return 0;
    fo(i, 1, T) if(bz[i])
        dis[i] += minh;
    return 1;
}