残余グラフの最速データ構造

Question

私は数千のノードとエッジを持つフローアルゴリズムを実装しようとしています。したがって、効率的なデータ構造が必要です。現在、私は次の操作を行います。

構造ノード：私はBFSを実行したときに、私はのためのresidual graph（基本的に後方エッジにエッジを見てする必要がありますノードvを与え

Double Linked Array (Parents) //Edges that enter the node (basicaly a tuple that contains a pointer to the parent node and the weight, current flow of the edge 
Double Linked Array (Sons) //Edges that leave the node 

問題は、あります私が平行なエッジを持つことができるので、どの前方エッジから後方エッジが来るかを常に知る必要があります。

現在、私はSons（v）のすべてのエッジを最初に処理して問題を解決しています。次に、すべてのエッジの宛先ノードw内の親（w）のインデックスを私に与えるマップを定義しました。したがって、私は格納されたバックエッジを取得し、アルゴリズムを実行することができます。しかし、これらのマップにはログ（E）アクセス時間があり、アルゴリズムが遅くなりすぎます。どのように私はこの問題にアプローチする必要があります（二重リンクリストはstd :: vectorとして実装されています）？

Answer 1

私が使用して表現はエッジリストのようなものであるが、追加の情報を

typedef long long dintype; 
struct edge{ 
    edge(int t_ = 0,int n_ = 0, dintype c_ = 0){ 
    to = t_; 
    next = n_; 
    cap = c_; 
    } 
    int to,next; 
    dintype cap; 
}; 
const int max_edges = 131010; 
const int max_nodes = 16010; 
edge e[max_edges]; 
int first[max_nodes]; // initialize this array with -1 
int edges_num; 
inline void add_edge(int from,int to, dintype cap){ 
    if(edges_num == 0){ 
    memset(first,-1,sizeof(first)); 
    } 
    e[edges_num].to = to;e[edges_num].cap = cap; 
    e[edges_num].next = first[from];first[from] = edges_num++; 

    e[edges_num].to = from;e[edges_num].cap = 0; 
    e[edges_num].next = first[to];first[to] = edges_num++; 
} 

私は良いアイデアを説明することができるようにグローバル配列を使用していました。私はdinitz algorithmにこれを使用します。

ここで少し説明します。配列 "e"では、すべての辺を保持しています。最初の配列[v]では、配列eのvから出て行く最初の辺のインデックスを保持しています。配列eのインデックスidxにエッジが存在する場合、その逆エッジはインデックスidx^1の要素に格納されます。 したがって、この表現により、隣人リスト（最初の[v]から始まり、-1になるまで次のインデックスをたどる）と、一定時間内に逆のエッジにアクセスできることの両方が可能になります。

Answer 2

int src,snk,nnode,nedge; 
int fin[100000],dist[100000];//nodes 
int cap[100000],next[100000],to[100000]; 
void init(int s,int sn,int n) 
{ 
    src=s,snk=sn,nnode=n,nedge=0; 
    memset(fin,-1,sizeof(fin)); 
} 
void add(int u,int v,int c) 
{ 
    to[nedge]=v,cap[nedge]=c,next[nedge]=fin[u],fin[u]=nedge++; 
    to[nedge]=u,cap[nedge]=0,next[nedge]=fin[v],fin[v]=nedge++; 
} 
bool bfs() 
{ 
    int e,u,v; 
    memset(dist,-1,sizeof(dist)); 
    dist[src]=0; 
    queue<int> q; 
    q.push(src); 
    while(!q.empty()) 
    { 
     u=q.front(); 
     q.pop(); 
     for(e=fin[u];e>=0;e=next[e]) 
     { 
      v=to[e]; 
      if(cap[e]>0&&dist[v]==-1) 
      { 
       dist[v]=dist[u]+1; 
       q.push(v); 
      } 
     } 
    } 
    if(dist[snk]==-1) 
     return false; 
    else 
     return true; 
} 
int dfs(int u,int flow) 
{ 
    if(u==snk) 
     return flow; 
    int e,v,df; 
    for(e=fin[u];e>=0;e=next[e]) 
    { 
     v=to[e]; 
     if(cap[e]>0&&dist[v]==dist[u]+1) 
     { 
      df=dfs(v,min(cap[e],flow)); 
      if(df>0) 
      { 
       cap[e]-=df; 
       cap[e^1]+=df; 
       return df; 
      } 
     } 
    } 
    return 0; 
} 
int dinitz() 
{ 
    int ans=0; 
    int df,i; 
    while(bfs()) 
    { 
     while(1) 
     { 
      df=dfs(src,INT_MAX); 
      if(df>0) 
       ans+=df; 
      else 
       break; 
     } 
    } 
    return ans; 
} 

これは、init関数は、隣接リスト アドオンがリストに新しいエッジを追加して初期化し、フィンはそうuは内のすべての要素にアクセスできる隣接リスト の最後のノードを与え、ここでdinitzアルゴリズム のための私のコードです次のループ

uは、隣接する要素uが Vを見つけたいの最大フローを見つけながらもU に隣接する要素を与えるuは、前方エッジと後方エッジの両方を必要とするノードである

for(e=fin[u];e>=0;e=next[e]) 
{ 
    v=to[e]; 
} 

てリストしたがって、前方エッジがe であると仮定して、後方エッジはe^1であり、その逆もありますが、エッジの開始インデックスはゼロでなければなりません。