网络流小结①

其实网络流去年就刷了很多题 感觉也还不错
但是因为去年刷完网络流专题不知道为什么后面就一直没刷到网络流的题
导致noi那题水爆了的网络流(比起其他题= =)都没做出来!!!
唉╮(╯▽╰)╭
so这几天刷了一些网络流题目
也在和队长的交流(单方面询问。。 在这感谢下队长~)中学了一点东西
一个是zkw费用流 还有强制满流处理负费用环 退流使之达到流量收支平衡 也可以处理上下界流的问题

在这里做一个小结<这里只放zkw 剩下到下篇吧。。>
————————–zkw费用流————————
这个算法我去年看了一下 感觉好像很碉堡 又看不懂 今年在队长的讲解后终于懂了。。
它的思想就是先用一次spfa处理出每个点的dist值 再用sap的多流增广去增广
另附spfa三个优化
①(这个只针对于zkw费用流)正常的求dist是求离s的dist 但是如果求对t的dist会更快
这看似挺科学的 因为你在sap的时候是从s开始增广 如果是求对t的dist 就会有很对点的dist是inf 可以省一点时间
②SLF(Small Label First  ) 优化:思想是把spfa原来的单纯队列环成双端队列
每次插入元素时 比较新元素和当前队首元素的dist 如果新dist<队首dist 就插在队首 否则插在队尾
③LLL(Large Label Last)优化:思想是对于一个将被松弛的节点 如果它的dist > 平均dist 就把它扔到队尾 以后再松弛
直到有一个节点的dist<=平均dist 就进行松弛

因为③比较难打(其实就多了10多行吧 就是写起来比较蛋疼= = 后面有两个的程序) 所以一般只用①② 如果被卡了就上③吧。。

然后直接上程序吧。。
————–spfa(①②③)———–

int spfa()
{
  memset(dist, 0x7f, sizeof(dist));
  memset(b, 0, sizeof(b));
  q.push_front(t);
  dist[t] = 0;
  b[t] = 1;
  int sum = 0;
  while (!q.empty())
  {
    int now = q.front();
    while (dist[now] * q.size() > sum)
    {
      q.pop_front();
      q.push_back(now);
      now = q.front();
    }
    q.pop_front();
    sum -= dist[now];
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (!li[li[i].opt].v || dist[to] <= dist[now] – li[i].c) continue;
      if (b[to])
      {
        sum -= dist[to];
        dist[to] = dist[now] – li[i].c;
        sum += dist[to];
      }
      else
      {
        dist[to] = dist[now] – li[i].c;
        sum += dist[to];
        b[to] = 1;
        if (q.empty() || dist[to] < dist[q.front()]) q.push_front(to);
        else q.push_back(to);
      }
    }
    b[now] = 0;
  }
  return dist[s];

}

//41行
—————spfa(①②)———–

int spfa()
{
  memset(dist, 0x7f, sizeof(dist));
  memset(b, 0, sizeof(b));
  q.push_front(t);
  dist[t] = 0;
  b[t] = 1;
  while (!q.empty())
  {
    int now = q.front();
    q.pop_front();
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (!li[li[i].opt].v || dist[to] <= dist[now] – li[i].c) continue;
      dist[to] = dist[now] – li[i].c;
      if (!b[to])
      {
        b[to] = 1;
        if (q.empty() || dist[to] < dist[q.front()]) q.push_front(to);
        else q.push_back(to);
      }
    }
    b[now] = 0;
  }
  return dist[s];

}
//26行
——————–sap——————-

int sap(int now, int maxf)
{
  if (now == t) return maxf;
  int tot = 0;
  b[now] = 1;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (!b[to] && dist[to] == dist[now] – li[i].c && li[i].v)
    {
      int t = sap(to, min(maxf – tot, li[i].v));
      li[i].v -= t;
      li[li[i].opt].v += t;
      tot += t;
    }
  }
  return tot;
}

—————–ZKE_CF—————
int ZKW_CF()

{
  int ans = 0, m;
  while (spfa() != inf)
    while (m = sap(s, inf))
    {
      memset(b, 0, sizeof(b));
      ans += m * dist[s];
    }
  return ans;
}

网络流小结①》上有1条评论

发表评论