ネットワークフロー関連アルゴリズムテンプレート

テンプレートはすべて「チャレンジプログラムデザインコンテスト」から来ています.
1.最大ストリームアルゴリズム
2.Dinicアルゴリズム

//     Dinic  
#define INF 0x7fffffff
#define MAX_V 405
//         (  、  、   )
struct edge
{
    int to,cap,rev;
};

vector G[MAX_V];//       
int level[MAX_V];//          
int iter[MAX_V];//   ，            

//        from to    cap  
void add_edge(int from,int to,int cap)
{
    G[from].push_back((edge){to,cap,G[to].size()});
    G[to].push_back((edge){from,0,G[from].size()-1});
}

//  BFS            
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue que;
    level[s]=0;
    que.push(s);
    while(!que.empty()){
        int v=que.front();
        que.pop();
        for(int i=0;i0&&level[e.to]<0){
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
}

//  DFS     
int dfs(int v,int t,int f)
{
    if(v==t) return f;
    for(int &i=iter[v];i0&&level[v]0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}

//   s t    
int max_flow(int s,int t)
{
    int flow=0;
    for(;;){
        bfs(s);
        if(level[t]<0) return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dfs(s,t,INF))>0){
            flow+=f;
        }
    }
}
//  

2.二分図マッチング
1.コード2

//       
#define MAX_V 1005

int V;//   
vector G[MAX_V];//       
int match[MAX_V];//      
bool used[MAX_V];//DFS        

//         u v  
void add_edge(int u,int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}

//  DFS     
bool dfs(int v)
{
    used[v]=true;
    for(int i=0;i

3.最小費用の流れ
1.コード1
時間の複雑さはO(F 124 V 124)(Fは流量)である.

#define INF 0x7fffffff
//       
#define MAX_V 1005

//         (  ，  ，     )
struct edge
{
    int to,cap,cost,rev;
};

int V;//   
vector G[MAX_V];//       
int dist[MAX_V];//    
int prevv[MAX_V],preve[MAX_V];//              

//        from to   cap   cost  
void add_edge(int from,int to,int cap,int cost)
{
    G[from].push_back((edge){to,cap,cost,G[to].size()});
    G[to].push_back((edge){from,0,-cost,G[from].size()-1});
}
//   s t   f      
//          -1
int min_cost_flow(int s,int t,int f)
{
    int res=0;
    while(f>0){
        //  Bellman-Ford     s t    
        fill(dist,dist+V,INF);
        dist[s]=0;
        bool update=true;
        while(update){
            update=false;
            for(int v=0;v0&&dist[e.to]>dist[v]+e.cost){
                        dist[e.to]=dist[v]+e.cost;
                        prevv[e.to]=v;
                        preve[e.to]=i;
                        update=true;
                    }
                }
            }
        }
        if(dist[t]==INF){
            //     
            return -1;
        }
        // s t        
        int d=f;
        for(int v=t;v!=s;v=prevv[v]){
            d=min(d,G[prevv[v]][preve[v]].cap);
        }
        f-=d;
        res+=d*dist[t];
        for(int v=t;v!=s;v=prevv[v]){
            edge &e=G[prevv[v]][preve[v]];
            e.cap-=d;
            G[v][e.rev].cap+=d;
        }
    }
    return res;
}
//  

例題http://poj.org/problem?id=2135/
2.コード2
時間の複雑さはO(F 124 V 124)です.O(F 124 V 12462)かもしれません.

#define INF 0x7fffffff
//       
#define MAX_V 1005

typedef pair P;//first      ，second      
//         (  ，  ，     )
struct edge
{
    int to,cap,cost,rev;
};

int V;//   
vector G[MAX_V];//       
int h[MAX_V];//    
int dist[MAX_V];//    
int prevv[MAX_V],preve[MAX_V];//              

//        from to   cap   cost  
void add_edge(int from,int to,int cap,int cost)
{
    G[from].push_back((edge){to,cap,cost,G[to].size()});
    G[to].push_back((edge){from,0,-cost,G[from].size()-1});
}
//   s t   f      
//          -1
int min_cost_flow(int s,int t,int f)
{
    int res=0;
    fill(h,h+V,0);//   h
    while(f>0){
        //  Dijkstra    h
        priority_queue
,greater
 > que;
        fill(dist,dist+V,INF);
        dist[s]=0;
        que.push(P(0,s));
        while(!que.empty()){
            P p=que.top();
            que.pop();
            int v=p.second;
            if(dist[v]
0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
                    dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
                    prevv[e.to]=v;
                    preve[e.to]=i;
                    que.push(P(dist[e.to],e.to));
                }
            }
        }
        if(dist[t]==INF){
            //     
            return -1;
        }
        for(int v=0;v