c++ - 残差图的最快数据结构

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 我需要查看 residual graph 中的边(基本上是你发送流的边缘的向后边缘)，留下 v。因为我可以有平行边缘，所以我需要始终知道哪个向后边缘来自哪个向前边缘。

目前，我正在通过首先处理 Sons(v) 中的所有边来解决问题，然后我定义了一个映射，该映射为我提供了所有这些边的目标节点 w 中 Parents(w) 的索引。因此我得到了我存储的后向边缘并且可以执行我的算法。然而，这些 map 的访问时间为 log(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;
}

这是我的dinitz算法代码 这里 init 函数初始化邻接表 add 在列表中添加一条新边，fin 给出该邻接列表中的最后一个节点 所以你可以通过以下循环访问列表中的所有元素

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

其中u是你要查找其相邻元素的节点 v 将把相邻的元素给 u 同样在找到最大流量时你需要前向边缘和后向边缘 所以假设前缘是 e 那么向后的边缘将为 e^1，反之亦然，但为此，边缘的起始索引应为零