【図論】最大ストリームのEKアルゴリズムとDinicアルゴリズムおよび最小費用最大ストリーム

最大ストリーム:
1枚のネットワーク図を与えて、そしてソース点と終点を指定して、すべての辺はすべてその容量があって、起点は無限の流量を持っていて、ソース点から通るすべての経路の最終的な到着の汇点の最大の流量とを求めます.同一ノードについては、流入する流量の和が流出する流量の和が同一であり、すなわち、ノード1に12流量がノード2に流入し、ノード2にそれぞれ8流量がノード3,4流量がノード4に流入する場合に可能である. 
EKアルゴリズム:
一方,EKアルゴリズムは,ソース点sから集約点tまでの間の広がり経路を繰り返し探索し,あれば広がり経路上の各セグメント[容量−流量]の最小値deltaを探索し,なければ終了する.また、残りのネットワークの値(逆エッジに関連)を更新します.すべての順方向エッジからdeltaを減算し、すべての逆方向エッジにdeltaを加算する.リバースエッジには容量があるので、次回は拡張パスを探してリバースエッジを歩くことができます.この設計により、以前の操作を相殺し、総流量を増加させるのに適したエッジを見つけることができ、プログラムに後悔と修正の機会を与えることができます.deltaが見つかったら、最大ストリーム値にdeltaを加え、現在の最大ストリーム値に更新します.

int maxData = 0x7fffffff;
int capacity[arraysize][arraysize]; //         
int flow[arraysize];                //                    
int pre[arraysize];                 //               ,             
int n,m;
queue myqueue;
int BFS(int src,int des)
{
    int i,j;
    while(!myqueue.empty())       //    
        myqueue.pop();
    for(i=1;i0 && pre[i]==-1)
            {
                 pre[i] = index; //    
                 flow[i] = min(capacity[index][i],flow[index]);   //  ：       
                 myqueue.push(i);
            }
        }
    }
    if(pre[des]==-1)      //            
        return -1;
    else
        return flow[des];
}
int maxFlow(int src,int des)
{
    int increasement= 0;
    int sumflow = 0;
    while((increasement=BFS(src,des))!=-1)
    {
         int k = des;          //        
         while(k!=src)
         {
              int last = pre[k];
              capacity[last][k] -= increasement; //        
              capacity[k][last] += increasement; //        
              k = last;
         }
         sumflow += increasement;
    }
    return sumflow;
}
int main()
{
    int i,j;
    int start,end,ci;
    while(cin>>n>>m)
    {
        memset(capacity,0,sizeof(capacity));
        memset(flow,0,sizeof(flow));
        for(i=0;i>start>>end>>ci;
            if(start == end)               //           
               continue;
            capacity[start][end] +=ci;     //                   
        }
        cout<

Dinicアルゴリズム:
最も核心的な内容は多重化である.全体図の階層化,すなわちソース点が第1層であり,ソース点に接続され容量のある点が第2層であり,第2層に接続され容量のある点が第3層である......終点に到達できなければ,拡張経路が見つからないことを示し,このときも最大ストリームに達した.一回のBFSは何度も広がります.効率はEKアルゴリズムよりも大幅に向上した. 

Dinic              。         ，  BFS       。    EK      。 
*/ 
int tab[250][250];//     
int dis[250];//     ,    
int q[2000],h,r;//BFS   , ,  
int N,M,ANS;//N:  ;M,   
int BFS()
{
     int i,cur;
     memset(dis,-1,sizeof(dis));// -1   
     dis[1]=0;
     head=0;tail=1;
     que[0]=1;//     
     while (head0)
               {
                  dis[i]=dis[cur]+1; 
                  que[tail++]=i;
               }
     }
     if (dis[N]>0)
        return 1;
     else
        return 0;//   DIS   ,  BFS     
}
//Find      ,           ,  0       
int find(int x,int low)//Low         (      )       
{
    int i,a=0;
    if (x==N)return low;//    
    for (i=1;i<=N;i++)
    if (tab[x][i] >0 //   
     && dis[i]==dis[x]+1 //         
     &&(a=find(i,min(low,tab[x][i]))))//    (a <> 0) 
    {
       tab[x][i]-=a;
       tab[i][x]+=a;
       return a;
    }
    return 0;
    
}
int main()
{
    //freopen("ditch.in" ,"r",stdin );
    //freopen("ditch.out","w",stdout);
    int i,j,f,t,flow,tans;
    while (scanf("%d%d",&M,&N)!=EOF){
    memset(tab,0,sizeof(tab));
    for (i=1;i<=M;i++)
    {
        scanf("%d%d%d",&f,&t,&flow);
        tab[f][t]+=flow;
    }
    //
    ANS=0;
    while (BFS())//         ,  BFS        
    {
          while(tans=find(1,0x7fffffff))ANS+=tans;//  BFS        ,        
    }
    printf("%d
",ANS);
    }
    system("pause");
}

最小費用最大フロー:最大フローに複数の解がある場合、各エッジに単位費用の量を添付し、最大フローを満たす場合の最小費用はいくらですか?
最小費用最大ストリームは、残りのネットワークに基づいて複数の費用ネットワークを追加するだけです.最大流に基づいて,費用を経路長と見なし,最短路を求めればよい.注意最初のリバースエッジの費用は、順方向エッジの負数です. 
例えばPOJ 2516という問題は、N個の供給者、M個の雇用者、K種の物品があります.各供給業者の各物品に対する供給量は既知であり、各雇用主の各物品に対する需要量は既知であり、異なる供給業者から異なる貨物を異なる雇用主に輸送するには異なる費用が必要であり、また供給業者Mjから第kind種貨物を送る単位数から雇用主Niに必要な単位費用が知られている.問:供給は需要を満たしていますか.もし満足すれば、最小運賃はいくらですか?コードはよく理解されていて、テンプレートとして使用できます.

int map[nMax][nMax];//map[i][j]      k   i   j     
int vis[nMax];//  i    
int cap[nMax][nMax];//  i j      
int dis[nMax];// i   
int que[nMax];//  
int pre[nMax];//          
int num,ans;//num     ，ans     
int spfa()//spfa     ，dijstra      ，      spfa
{
    int i,k;
    int head,tail;
    memset(vis, 0, sizeof(vis));
    for (i = 0; i <= num; ++ i)
    {
    dis[i] = inf;
    }
    dis[0] = 0;
    vis[0] = 1;
    head = tail = 0;
    que[tail++] = 0;
    while (head < tail)
    {
	    k = que[head];
	    vis[k] = 0;
	    for (i = 0; i <= num; ++ i)
	    {
	    	if (cap[k][i] && dis[i] > dis[k] + map[k][i])//  k i   ，       ，       
	    	{
			    dis[i] = dis[k] + map[k][i];
			    pre[i] = k;
			    if (!vis[i])
			    {
				    vis[i] = 1;
				    que[tail ++] = i;
			    }
	   		}
	    }
	    head ++;
    }
    if (dis[num] havek[i])//         ，          
    {
    flag = 0;
    break;
    }
    }
    ans = 0;
    num = N + M + 1;
    for (k = 1; k <= K; ++ k)//           ，    
    {
	    memset(cap, 0, sizeof(cap));
	    memset(map, 0, sizeof(map));
	    for (i = 1; i <= N; ++ i)
	    {
	    for (j = 1; j <= M; ++ j)
	    {
		    scanf("%d", &map[j][M + i]);// N     M+1-M+N   ，      ，map j M+i     j    i   
		    map[M + i][j] = -map[j][M + i];
		    cap[j][M + i] = have[j][k];//j i    k     place j     
		    cap[M + i][j] = 0;
	    }
	    }
	    if (!flag)
	    {
	   		continue;
	    }
	    for (i = 1; i <= M; ++ i)
	    {
		    cap[0][i] = have[i][k];//   place i      k    place i  
		    map[0][i] = map[i][0] = 0;//    i   0
	    }
	    for (i = 1; i <= N; ++ i)
	    {
		    cap[M + i][num] = need[i][k];//  i        i    k       。
		    map[M + i][num] = map[num][M + i] = 0;
	    }
	    while (spfa())//  k        
	    {
	    	end();
	    }
    }
    if (flag)
    {
    printf("%d
", ans);
    }
    else
    printf("-1
");
    }
    return 0;
}