BZOJ 3218: a + b Problem【当网络流遇上可持久化线段树】

首先搞二元关系
这个本来的关系是一坨点 是否有一个点选择了白 这个不好弄
可以转换成 是否全部选择了黑

对每个点i新建一个点i’
含义是 点i之前的a值在li~ri范围的点 是不是全部选了黑色
i’选择了全部选黑且范围内某个点选了白的代价是inf
i’选择了不是全部选择了黑且i选择了黑的代价是pi

这样就可以得到correct ans了

但是这个的边数是n^2级的 too大to过
把上面的方程解了可以发现 范围内的点要向i‘连inf的边 这个的边数是n^2的 这个就是瓶颈

怎么办呢=-=
经过黄神的提醒(边数是nlogn级的
突然想到了这题是不是可以用可持久化线段树= =
线段树的权值表示a的权值
线段树的一个节点都代表了网络流的一个节点
一个节点[t, l, r]表示1~t号节点中 a值在l~r的都向这个点直接或间接的连了inf的边
查询就是把线段树中代表1~i-1中的a值在li~ri间的节点向当前的i’连边 可以知道最多log个节点
插入就是 对于一个新的点i 权值为ai 在可持久化线段树中插入到ai位置
对于经过的新建的点t last_t->t连inf的边 i->t连inf的边 last_t是上个线段树t位置的这个节点
每次新建也是log个点 log条边
所以总边数、点数都是nlogn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 1000005;
const int inf = 0x3fffffff;
const int inf2 = 1000 * 1000 * 1000;

//===========================NetworkFlow===============

const int NFmaxn = 1000005;
const int NFmaxm = 1000005;
const int NFinf = 0x3fffffff;

struct NF_Line
{
  int to, next, v, opt;
};

struct Network_Flow
{
  NF_Line li[NFmaxm];
  int be[NFmaxn], l, s, t, n, num[NFmaxn], note[NFmaxn];

  void makeline(int fr, int to, int v)
  {
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].to = to;
    li[l].v = v;
    li[l].opt = l + 1;

    ++l;
    li[l].next = be[to];
    be[to] = l;
    li[l].to = fr;
    li[l].v = 0;
    li[l].opt = l - 1;
  }

  void create(int N)
  {
    n = N;
  }

  int sap(int now, int maxf)
  {
    if (now == t) return maxf;
    int mi = n, tot = 0;
    for (int i = be[now]; i; i = li[i].next)
    {
      int to = li[i].to;
      if (li[i].v && note[to] + 1 == note[now])
      {
        int k = sap(to, min(maxf - tot, li[i].v));
        li[i].v -= k;
        tot += k;
        li[li[i].opt].v += k;
        if (note[s] >= n || tot == maxf) return tot;
      }
      if (li[i].v) mi = min(mi, note[to]);
    }
    if (!tot)
    {
      if (!--num[note[now]])
      {
        note[s] = n;
        return 0;
      }
      ++num[note[now] = mi + 1];
    }
    return tot;
  }

  int query(int S, int T)
  {
    s = S, t = T;
    memset(num, 0, sizeof(num));
    memset(note, 0, sizeof(note));
    num[0] = n;
    int ans = 0;
    while (note[s] < n) ans += sap(s, NFinf);
    return ans;
  }

  void clear()
  {
    l = s = t = n = 0;
    memset(be, 0, sizeof(be));
    memset(num, 0, sizeof(num));
    memset(note, 0, sizeof(note));
  }
}nf;

//===========================NetworkFlow===============

struct node
{
    int l, r;
}t[maxn];

int n, m, root[maxn], tot, tot2, s, T, ans;

void query(int now, int l, int r, int lf, int rt, int p)
{
    if (!now) return;
    if (l >= lf && r <= rt)
    {
        nf.makeline(now, p, inf);
        return;
    }
    int mid = (l + r) / 2;
    if (lf <= mid) query(t[now].l, l, mid, lf, rt, p);
    if (rt >= mid + 1) query(t[now].r, mid + 1, r, lf, rt, p);
}

int ins(int no, int l, int r, int lr, int p)
{
    int now = ++tot;
    t[now] = t[no];
    if (no) nf.makeline(no, now, inf);
    nf.makeline(p, now, inf);
    if (l == r) return now;
    int mid = (l + r) / 2;
    if (lr <= mid) t[now].l = ins(t[no].l, l, mid, lr, p);
    else t[now].r = ins(t[no].r, mid + 1, r, lr, p);
    return now;
}

int main()
{
    scanf("%d", &n);
    s = ++tot, T = ++tot;
    for (int i = 1; i <= n; ++i)
    {
        int a, b, w, l, r, p, tp = ++tot, now = ++tot;
        scanf("%d%d%d%d%d%d", &a, &b, &w, &l, &r, &p);
        nf.makeline(tp, now, p);
        nf.makeline(s, now, w);
        nf.makeline(now, T, b);
        ans += w + b;
        query(root[i - 1], 0, inf2, l, r, tp);
        root[i] = ins(root[i - 1], 0, inf2, a, now);
    }
    nf.create(tot);
    printf("%d", ans - nf.query(s, T));
}

最小割小结

《浅析一类最小割问题(pty)》
这算是个解决最小割问题比较统一的方法吧 感觉是很厉害O.O
这个就是把最小割模型都转化成二元关系:(x,y)
x,y都取 代价为v1
x,y都不取 代价为v2
x取y不取 代价为v3
x不取y取 代价为v4
对于这个图233

a + b = v1
c + d = v2
a + d + f = v3
b + c + e = v4

令K = v3 + v4 – v1 – v2

如果 K < 0 那么关系图要是二分图就能做 把一侧的定义相反即可(这个的题目很少 不详写= = 首先要保证边权是非负的 K >= 0 e和f一定是非负的
可以看到每个等式中都出现了a、c中的一个 b、d中的一个
如果a、c中有边权是负的 可以把它们同时加上一个数 最后再扣掉
b、d同理
还有最好保证他们都是整数
如果出现小数 可以把所有边权都*=分母的最小公倍数 最后再除掉 (这个最小公倍数一般是2什么的= =)
然后就可以直接建图了

对于一些一元关系 某个点取有多少获利 不取有多少获利什么的 最后直接建边即可
这里对每对二元和一元关系的建边是独立的 最后再把边权加起来作为边权(不加也可以) 而不是比如对于每个二元关系s->p的权值都是一样的

注意这里求的是最小割 是最小值 有的题目求的是最大获利
有两种转化方法
一是把权值取负 然后求最小获利
二是比如你取了某个点 说明你不能不取这个点 就失去了不取这个点能获得的获利 这样就变成了最小代价了 然后最后把权值和-最小代价就是最大收益
↑其实这两个方法好像是等价的 看你怎么理解罢了=-=

==========BZOJ 3438: 小M的作物===========
这题是一个多元关系 但是也可以转成一元的
对于每个作物 s到它的边表示这个作物选择A 到t的边表示选择b
对于每个组合 新建两个点
一个点表示这些点是否全部选了A 这个点选择是的收益是c1i 否的收益是0
另外一个表示这些点是否全部选了B 这个点选择是的收益是c2i 否的收益是0
s到第一个点的边表示 是全部取A 到第二个点的边表示 不是全部取B
第一个点到t的边表示 不是全部取A 第二个点到t的边代表 是全部取B
如果第一个点选择了全部取了A 但是组合里的某个作物选择了B 这样的代价就是inf 因为是不可行的= =
对于B同理
这样就把多元关系转成了二元关系 很多多元关系的题目都可以用这个思路
然后把这个方程列啊列 最后建出来的图是一个类似最大权闭合子图的东西O.O

==========BZOJ 2127: happiness===========
这个就是非常模板的题
说一点0 0
在很多情况下可以设e=f(比如这题)
但是也有的时候设两个变量比较方便(比如上面那题) 自己看着办吧233

==========BZOJ 3218: a + b Problem===========
这题是厉害啊 我决定为这题独立开一篇文章 以表(pian)敬(I)意(P)

BZOJ 2521: [Shoi2010]最小生成树

这题就是求最少要多少代价可以让一条指定边必为最小生成树上边
每次可以吧某条边权+1 代价为1
可以转化为求去掉权值大于指定边权的边后 最少要多少代价可以使指定边变为割边
即求新图去掉指定边的最小割!!!

每条边的权为V + 1 -line[i].v (要使这条边去掉就是把它升到比指定边权值高)
用最大流水过

发现很久没打网络流了= =、。。
下星期开始怒刷网络流~~~~~~~~~

—————–code——————-

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
const int maxn = 1005;
struct inp
{
  int fr, to, v;
}a[maxn];
struct line
{
  int to, next, v, opt;
}li[100000];
int be[maxn], t, s, n, l, x, m, dinic[maxn], num[maxn];
int sap(int now, int maxf)
{
  if (now == t) return maxf;
  int tot = 0;
  int mi = n;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (li[i].v > 0 && dinic[to] + 1 == dinic[now])
    {
      int t = sap(to, min(li[i].v, maxf – tot));
      tot += t;
      li[i].v -= t;
      li[li[i].opt].v += t;
      if (tot == maxf || dinic[s] >= n) return tot;
    }
    if (li[i].v > 0) mi = min(mi, dinic[to]);
  }
  if (!tot)
  {
    if (!–num[dinic[now]])
    {
      dinic[s] = n;
      return 0;
    }
    ++num[dinic[now] = mi + 1];
  }
  return tot;
}
void makeline(int fr, int to, int v, int opt)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].v = v;
  li[l].to = to;
  li[l].opt = opt;
}
int main()
{
  freopen(“input.in”,”r”,stdin);
  freopen(“output.out”,”w”,stdout);
  cin >> n >> m >> x;
  s = 0;
  t = 1000;
  inp va;
  for (int i = 0; i < m; i++)
  {
    scanf(“%d%d%d”, &a[i].fr, &a[i].to, &a[i].v);
    if (i + 1 == x) va = a[i];
  }
  makeline(s, va.fr, 0x7fffffff, l + 2);
  makeline(va.fr, s, 0, l);
  makeline(va.to, t, 0x7fffffff, l + 2);
  makeline(t, va.to, 0, l);
  for (int i = 0; i < m; i++)
    if (a[i].v <= va.v && i + 1 != x)
    {
      makeline(a[i].fr, a[i].to, va.v + 1 – a[i].v, l + 2);
      makeline(a[i].to, a[i].fr, va.v + 1 – a[i].v, l);
    }
  n += 2;
  num[0] = n;
  int ans = 0;
  while (dinic[s] < n) ans += sap(s, 0x7fffffff);
  cout << ans;
  fclose(stdin);fclose(stdout);
}