Самая быстрая структура данных для остаточных графов

Question

Я пытаюсь реализовать алгоритм потока с тысячами узлов и ребер, поэтому мне нужны эффективные структуры данных. В настоящее время я делаю следующее:

Узел структуры:

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

Проблема в том, что когда я выполняю BFS, учитывая узел v, мне нужно смотреть на ребра в остаточном графе (в основном это задние ребра для ребер, на которые вы посылаете поток), которые оставляют Поскольку у меня могут быть параллельные ребра, мне нужно всегда знать, какой задний край идет от какого переднего края.

В настоящее время я решаю эту проблему, сначала обработав все ребра в Sons (v), а затем я определил карту, которая дает мне индекс Родителя (w) в узле назначения w всех этих ребер. Поэтому я получаю задний фронт, который сохранил, и могу выполнить свой алгоритм. Однако эти карты имеют время доступа к журналу (E), что слишком сильно замедляет мой алгоритм. Как мне подойти к этой проблеме (двойные связанные списки реализованы как std :: vector)?

Answer 1

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 инициализирует список смежности add добавляет новое ребро в список, а fin дает последний узел в этом списке смежности. так что вы можете получить доступ ко всем элементам в списке с помощью следующего цикла

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

где u - узел, соседний элемент которого вы хотите найти v передаст смежный элемент к вам Кроме того, при поиске максимального потока вам понадобится как передний край, так и задний край. поэтому предположим, что передний край тогда обратное ребро будет е ^ 1 и наоборот, но для этого начальный индекс для ребер должен быть нулевым

Answer 2

Представление, которое я использую, является чем-то вроде списка границ, но с дополнительной информацией

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

Я использовал глобальные массивы, чтобы лучше объяснить идею.Я использую это для моего алгоритма Диница .

Теперь немного пояснений.В массиве «е» я держу все ребра.В массиве first [v] я храню индекс первого ребра, выходящего из v в массиве e.Если ребро присутствует в индексе idx в массиве e, то обратное ребро сохраняется в элементе с индексом idx ^ 1.Таким образом, это представление позволяет нам иметь список соседей (начиная с первого [v] и следующего за индексом, пока он не станет равным -1) и иметь возможность доступа к обратному фронту в постоянное время.