uva 10330 (최대 흐름 & 슈퍼 소스 집합 점 의 구축 & EK 알고리즘)

제목: 제목: 한 장의 방향 도 는 n 개의 점 으로 구성 되 고 모든 점 은 하나의 용량 제한 이 있 으 며 그 다음 에 여러 개의 원점 과 여러 개의 어 셈 블 리 점 을 제시 하고 두 점 사이 에 도 용량 제한 이 있다.DHAKA 에 최대 얼마나 많은 에 너 지 를 전달 할 수 있 는 지 물 었 다.
사고방식: 처음으로 인터넷 흐름 문 제 를 한다.오래 했 어 요.우선 이 문 제 는 여러 개의 원점 과 여러 개의 어 셈 블 리 점 이 있 기 때문에 하나의 슈퍼 원점 과 슈퍼 어 셈 블 리 점 을 구축한다.슈퍼 소스 에서 모든 소스 까지 의 용량 제한 은 무한대 이 고 모든 외환 점 에서 슈퍼 외환 점 까지 의 용량 제한 도 무한대 이다.bfs 를 이용 하여 확대 경 로 를 찾 으 면 출발점 에서 종점 까지 이 길이 갈 수 있 는 최소 유량 을 찾 을 수 있 습 니 다. 모든 확대 경로 의 점 은 변 화 를 해 야 합 니 다. 비 확대 경로 의 점 은 변 하지 않 아 도 됩 니 다.어떻게 바 뀌 지?전방 향 호의 유량 은 이 최소 유량 을 더 해 야 한다. 역방향 호의 유량 은 이 최소 유량 을 빼 야 한다. 현재 방향 호의 유량 = 용량 또는 역방향 호의 유량 = 0 일 때 이 길 은 더 이상 갈 수 없다.만약 길 을 찾 지 못 하면 종점, 즉 종점 의 잔류 = 0 까지 갈 수 있다 면 현재 의 유량 은 가장 큰 유량 이다.코드:

#include <iostream>
using namespace std;
#include <stdio.h>
#include <cstring>
#include <queue>

const int N = 210;
const int INF = 0x3f3f3f3f;

int leave[N];
int pre[N];
int c[N][N],f[N][N];
int n;

int EK() {
    memset(f,0,sizeof(f));
    memset(pre,0,sizeof(pre));
    int F = 0;
    queue<int> q;
    while(1) {
        memset(leave,0,sizeof(leave));
        q.push(0);
        leave[0] = INF;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
            for(int i = 0; i < 2 *n + 2; i++) {
                if(!leave[i] && c[u][i] > f[u][i]) {
                    pre[i] = u;
                    q.push(i);
                    leave[i] = min(leave[u],c[u][i] - f[u][i]);
                }
            }
        }
        if(leave[2 * n + 1] == 0)
            return F;

        for(int u = 2 * n + 1; u != 0; u = pre[u]) {
            f[pre[u]][u] += leave[2 *n + 1];
            f[u][pre[u]] -= leave[2 *n + 1];
        }
        F += leave[2 *n + 1];

    }
}
int main() {

    int edge,b,d;
    int u,v,cap;
    while(scanf("%d",&n) != EOF) {
        memset(c,0,sizeof(c));
        for(int i = 1; i <= n; i++)
            scanf("%d",&c[i][i + n]);//       ，            

        scanf("%d",&edge);
        for(int i = 0; i < edge; i++) {
            scanf("%d%d%d",&u,&v,&cap);
            c[u + n][v] = cap;//      ，     i + n              c[u][v]       。
        }
        scanf("%d%d",&b,&d);
        for(int i = 0 ; i < b; i++) {
            scanf("%d",&u);
            c[0][u] = INF;//       0
        }
        for(int i = 0; i < d; i++) {
            scanf("%d",&u);
            c[u + n][2 * n + 1] = INF;//       2 * n + 1
        }
        printf("%d
",EK());
    }
    return 0;
}