네트워크 흐름 초기 화

네트워크 흐름 의 정의
방향 그래프 G = (V, E) 중:
• 유일한 것 이 있다
원점 S (입 도 는 0: 출발점)
• 유일한 것 이 있다
어 셈 블 리 T (출 도 0: 끝 점)
• 그림 속 의 모든 호 (u, v) 는 마이너스 가 있다.
용량 c (u, v)
상기 조건 을 만족 시 키 는 그림 G 를 네트워크 흐름 도 라 고 한다.
G = (V, E, C)
1. 실행 가능 흐름
◆ 각 호 (u, v) 에 실수 f (u, v) 를 정 하고 만족: 0 < = f (u, v) < = c (u, v) 가 있 으 면 f (u, v) 를 호 (u, v) 의 유량 이 라 고 부른다.
◆ 데이터 만족 조건 이 있다 면:
          원점 s:  유출 량
          합류점 t:   유 입 량
          중간 점: 총 유 입 량 = 총 유출 량
    그러면 전체 네트워크 의 데이터 가 실행 가능 한 흐름 이 된다.
2. 최대 흐름
• 모든 실행 가능 한 흐름 중에서 유량 이 가장 큰 흐름 의 유량
  그림 2 에서 7 도 최대 흐름 이다.
• 최대 흐름 은 하나 가 아 닐 수도 있 습 니 다.
2. 최대 흐름 알고리즘
◆ 포드 - 풀 커 슨 (포드 - 포크 슨) 알고리즘:
단계:
(1) 확대 경로 가 존재 하면 확대 경 로 를 찾 아 라.
(2) 그리고 이 확대 경 로 를 따라 데이터 업데이트 (데이터 증가)
1. 확대 경로
•
s 에서 t 까지 의 간단 한 경로 입 니 다. 만약 에 변 (u, v) 의 방향 이 이 경로 의 방향 과 일치 하면 (u, v) 을 정방 향 변 이 라 고 부 르 고 방향 이 일치 하지 않 을 때 역방향 변 이 라 고 부 릅 니 다.
경로 의 모든 변 이 만족 하면:
① 모든 정방 향 변 에는 f (u, v) < c (u, v)   　                                                                                    　    ② 모든 역방향 은 f (u, v) > 0
이 경 로 를 하나 라 고 합 니 다.
확장 경로 (트 래 픽 증가 가능)
2. 확대 경 로 를 따라 확대
1）  먼저 d 를 정 무한 으로 설정 합 니 다.
        하면, 만약, 만약...
                d  = min ( d, c ( u, v ) – f (u, v ) )
        역방향
                d  = min ( d, f ( u, v ) )
2) 이 확장 경로 의 가장자리
         만약 (u, v) 이 정방 향 변 이 라면 f (u, v) = f (u, v) + d;
         만약 (u, v) 이 역방향 변 이 라면 f (u, v) = f (u, v) – d;
확대 후 총 유량 이 d 증가 하 였 다.
• 정리:
실행 가능 한 흐름 f 는 최대 흐름 이 며, f 에 대한 확장 경로 가 존재 하지 않 을 때 만
증: 만약 에 f 가 최대 흐름 이지 만 그림 에 f 의 확대 경로 가 존재 한다 면 이 확대 경 로 를 따라 확대 할 수 있 고 더 큰 흐름 을 얻 을 수 있 으 며 f 와 최대 흐름 의 모순 이다.따라서 최대 흐름 은 확장 경로 가 존재 하지 않 는 다.
◆ 포드 - 풀 커 슨 방법 (광 류 증가) 최대 흐름 구하 기
 (포드 - 포크 슨)
단계:
(1) 확대 경로 가 존재 하면 확대 경 로 를 찾 아 라.
              DFS,BFS
(2) 그 다음 에 이 확대 경 로 를 따라 데 이 터 를 업데이트 한다.
           (트 래 픽 증가)
While  확장 경로 가 있다    do   이 경로 의 데이터 업데이트
반복 알고리즘
알고리즘 구현:
c [u, v]: 용량
유량
B [i]: 찾 은 확장 경 로 를 저장 하고 경로 의 노드 i 의 전구 노드 를 기록 합 니 다.
Sum: 최대 데이터.
가정: 1 은 원점 S 이다.환 점 T 입 니 다.

#include <iostream>
#include <algorithm>
#include <cstring>
#define OO 999999
using namespace std;

int c[100][100];//  
int f[100][100];//  
int b[100];     //        
int sum;
int n,m;

bool findflow(int k);
void addflow();

//  k       i
bool findflow(int k)
{
    if (k==n) return true;//         
    for (int i=1;i<=n;i++)
    {
        if ( b[i]==-1 && (c[k][i]-f[k][i]>0||f[i][k]>0) )
        {
            b[i]=k;
            if ( findflow(i) ) return true;
        }
    }
    return false;
}

//       
void addflow()
{
    int d=OO;
    int i=n;
    while ( b[i]!=0 )
    {
        if ( c[b[i]][i]>0 )
        {
            d=min(d,c[b[i]][i]-f[b[i]][i]);
        }
        if ( c[i][b[i]]>0 )
        {
            d=min(d,f[i][b[i]]);
        }
        i=b[i];
    }
    i=n;
    while ( b[i]!=0 )
    {
        if ( c[b[i]][i]>0 )
        {
            f[b[i]][i]+=d;
        }
        if ( c[i][b[i]]>0 )
        {
            f[i][b[i]]-=d;
        }
        i=b[i];
    }
    sum+=d;
}

int main()
{
    int x,y,z;
    cin >> n >> m;
    memset(c,-1,sizeof(c));
    memset(f,0,sizeof(f));
    for (int i=1;i<=m;i++)
    {
        cin >> x >> y >> z;
        c[x][y]=z;
    }
    for (int i=0;i<=n;i++) b[i]=-1;
    b[1]=0;
    while ( findflow(1) )
    {
        addflow();
        for (int i=0;i<=n;i++) b[i]=-1;
        b[1]=0;
    }
    cout << sum << endl;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (f[i][j]>0) cout << i << "-->" << j << " " << f[i][j] << endl;
        }
    }
    return 0;
}