That's talk about Network Flow

其實我一直以為我對網路流很瞭解了，

但其實有很多東西我還不會QQ

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝從最簡單的開始

首先，有一個作法，就是不斷的流，流到不能流就停止的FF算法

要注意的是你在邊的某方向流了多少，就可以在另一個方向多流一些!!!!（就是剩餘的概念）

他的證明很神奇，但也不是什麼想不到的事情，只要你注意到一個KEY：『最小割』，『流』一定會小於等於『割』，當兩者相等時，流必為最大的，割必為最小的，也就是所謂的『最大流最小割定理』。

每次選一條可以流的路 -> O(E)＊最慘的情況下每次只增加一，而最大流是F->O(F) = O(FE)

這樣實在是太悲劇了，完全無法預知，只要流量都大到暴，時限內根本跑不完QAQ

Dinic在好久好久以前，就做了一個很棒的改進，他發現只要每次都走最短路（是指距離最短，跟邊上的流量無任何關係），就可以有很精確的複雜度了（但通常會比較小）

希望我寫的不會太爛，如果不想去了解的話，可以直接記結果，也就是每次都走最短路的話，最多只會擴充O(VE)次。所以重要的就是怎麼去找最短路。如果你感到很疑惑，走不走最短路真的有差嘛？還是那只是理論值而已，說說罷了。這裡可以附上一個非常誇張的圖：

走最短路的話，就可以避免這種愚蠢的情形發生。想要找最短路的話主要有三種方法：

1. 用BFS找：俗稱Edmonds- Karp Algorithm

這個概念很簡單，對於每次擴展都BFS一次，複雜度O(VE*E)

2. 用BFS建分層圖找：又稱Dinic Algorithm

他是先建出一個分層圖，不斷的dfs找路走，一直到沒有辦法走為止，就更新一次分層圖，並重複上述步驟。因為最長的distance是V，所以只會更新分層圖V次，複雜度O(VE+VE*V)

3. 用Relabel建分層圖找：又稱Improved Shortest Path Algorithm

先假定每個人距離T的dis都是0，接下來就開始用DFS找最短增廣路，如果你發現，某個點的距離已經不是你所想的那樣了，就把它設成他應該的樣子（這裡會用到一個概念，也就是點的距離只會增不會減，正確性在先前已證過），每次增廣O(V)＊最大距離O(V)＊某距離要查找幾次O(E)＝複雜度O(VE*V)

ISAP code:

struct edge{int t,c,r;edge(){} edge(int _t,int _c,int _r){t=_t;c=_c;r=_r;}};
vector<edge> G[N];
int s, t, n;
int iter[N], d[N], gap[N];
int dfs( int p, int flow ){
    if( p == t ) return flow;
    for( int &i=iter[p]; i<SZ(G[p]); i++ ){
        edge &e=G[p][i];
        if( e.c > 0 && d[e.t] == d[p]-1 ){
            int f = dfs( e.t, min( e.c, flow ) );
            if( f ){ e.c -= f, G[e.t][e.r].c += f; return f; }
        }
    }
    if( (--gap[d[p]]) == 0 ) d[s]=n;
    else{
        d[p]=n;
        for( int i=0; i<SZ(G[p]); i++ ) if( G[p][i].c && d[p]>d[G[p][i].t]+1 ) d[p]=d[G[p][i].t]+1;
        gap[d[p]]++; iter[p]=0;
    }
    return 0;
}
int isap(){
    for( int ret=0; d[s]<n; ret+=dfs(s,INF) );
    return ret;
}