2012年8月11日 星期六

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;
}

沒有留言:

張貼留言