BZOJ 3112: [Zjoi2013]防守战线

线性规划 可以理解为有一堆不等式限制条件 和一个函数g 要求这个函数的极值
网络流可以解决某类线性规划问题
详见曹钦翔WC的线性规划与网络流
一个比较经典的建图方法是 noi志愿者招募的模型
要用这种建图 必须满足
将不等式进行一些变形后
每个变量出现且仅出现两次 且一次为正 一次为负

具体做法如下;
将原不等式加入松弛变量后 进行差分
对每个不等式建点
对于一个正变量所在的不等式 可以看作流量的流入
对于一个负变量所在的不等式 可以看作流量的流出
则可以把有负变量的不等式点连一条边到有正变量的不等式点
在函数g中 设这个变量的系数为vi 则把这条边费用设为vi
对于一个不等式 在加入松弛变量后 仍会有一个常数
如果这个常数为正 则从源点连到这个点一条边 流量上界为这个常数
如果为负则连向汇点
直接跑一遍费用流 答案即为函数的极值

但是这种做法对于原不等式必须满足系数矩阵上的一列上的值 不为0的必须相同且连续
这样差分后才会满足  每个变量出现且仅出现两次 且一次为正 一次为负 这个条件
like this:
psb (52)
(一种颜色上的数值都一样 且白色为0)

但是这题的系数矩阵是长这样的 = =  :

psb (3)

这样的话差分后毫无意义- –

于是0 0
我们就要用到传说中的对偶型
psb (52)
这个就是原问题系数矩阵及极值函数g的对应关系

对于原问题 可以描述为:
有一个工厂 它生产n种产品 第i种产品可以卖ci元
现在一共有m种材料 生产一个产品i 需要aij个材料j
每个材料的个数有上限 为bi
现在要求一种生产方案使得获利最多

这个问题的对偶问题 可以描述为:
你现在要找这个工厂购买原材料 第i种材料需要bi个 价格由你定
这个工厂会把材料卖给你 仅当它觉得不亏
即它把卖给你的材料拿去做产品的价值<=你收购做这个产品所需材料的价格和
求最少需要多少¥可以收购完

这两个问题为对偶问题 他们的答案算出来是一样的
问题转移的方法如那个表所示
这样可以使系数矩阵顺时针旋转90度~
就可以把这题的不可做的系数矩阵转为可以做的矩阵了

对于这题 新的问题可以描述为
给定M种志愿者,第i种工作区间是[Li, Ri],雇佣一次Di块。现在要保证第j天最多雇佣Cj个人,求最大总费用。 <from WQS>
然后直接做就行了
不过看贴吧好像这题对偶完就跟po3680一样了。。

还有这题据说会卡spfa so就写了个zkw。。
————————–code—————————

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn = 1005;
const int inf = 0x7fffffff;
struct line
{
  int to, next, v, c, opt;
}li[1000005];
int s, t, n, m, l, be[maxn], c[maxn], dist[maxn], b[maxn];
queue<int> q;
void makeline(int fr, int to, int v, int c, int opt)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
  li[l].v = v;
  li[l].c = c;
  li[l].opt = opt;
}
bool spfa()
{
  memset(b, 0, sizeof(b));
  memset(dist, 0x80, sizeof(dist));
  q.push(t);
  dist[t] = 0;
  b[t] = 1;
  while (!q.empty())
  {
    int now = q.front();
    q.pop();
    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;
        q.push(to);
      }
    }
    b[now] = 0;
  }
  return dist[s] != static_cast<int>(0x80808080);
}
int sap(int now, int maxf)
{
  if (now == t) return maxf;
  b[now] = 1;
  int tot = 0;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (b[to] || !li[i].v) continue;
    if (dist[now] – li[i].c == dist[to])
    {
      int t = sap(to, min(maxf – tot, li[i].v));
      li[i].v -= t;
      li[li[i].opt].v += t;
      tot += t;
    }
  }
  return tot;
}
int ZKW()
{
  int ans = 0;
  while (spfa())
    while (int t = sap(s, inf))
    {
      memset(b, 0, sizeof(b));
      ans += t * dist[s];
    }
  return ans;
}
int main()
{
 // freopen(“input.in”, “r”, stdin);
 // freopen(“output.out”, “w”, stdout);
  s = 0, t = 1004;
  scanf(“%d%d”, &n, &m);
  for (int i = 2; i <= n + 1; ++i)
    makeline(i, i – 1, inf, 0, l + 2),
    makeline(i – 1, i, 0, 0, l);
  for (int i = 1; i <= n; ++i)
  {
    scanf(“%d”, &c[i]);
    if (c[i] – c[i – 1] < 0)
    {
      makeline(s, i, c[i – 1] – c[i], 0, l + 2);
      makeline(i, s, 0, 0, l);
    }
    else
    {
      makeline(i, t, c[i] – c[i – 1], 0, l + 2);
      makeline(t, i, 0, 0, l);
    }
  }
  makeline(s, n + 1, c[n], 0, l + 2);
  makeline(n + 1, s, 0, 0, l);
  for (int i = 0; i < m; ++i)
  {
    int lf, r, v;
    scanf(“%d%d%d”, &lf, &r, &v);
    makeline(r + 1, lf, inf, v, l + 2);
    makeline(lf, r + 1, 0, -v, l);
  }
  printf(“%d”, ZKW());
  //fclose(stdin);fclose(stdout);

}

网络流小结①

其实网络流去年就刷了很多题 感觉也还不错
但是因为去年刷完网络流专题不知道为什么后面就一直没刷到网络流的题
导致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;
}