【World Finals】2001 G

【试题编号】
2001 G
【名称】
Fixed Partition Memory Management
【题目大意】
美食节
【算法讨论】
按时间拆点 网络流
【时空复杂度】
O(n)
O(netflow)
【code】

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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#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;
//===========================NetworkCostFlowZkw========
const int NCFZmaxn = 10005;
const int NCFZmaxm = 200005;
const int NCFZinf_ = 0x7f;
const int NCFZinf  = 0x7f7f7f7f;
struct par
{
  int a, b;
  par(int _a = 0, int _b = 0) : a(_a), b(_b) {}
}TO[NCFZmaxn];
struct NCFZ_Line
{
  int fr, to, next, v, c, opt;
};
struct Network_Cost_Flow_Zkw
{
  NCFZ_Line li[NCFZmaxm];
  int be[NCFZmaxn], l, s, t, dist[NCFZmaxn], b[NCFZmaxn];
  deque<int> q;
  void makeline(int fr, int to, int v, int c)
  {
    ++l;
    li[l].next = be[fr];
    be[fr] = l;
    li[l].fr = fr;
    li[l].to = to;
    li[l].v = v;
    li[l].c = c;
    li[l].opt = l + 1;
    ++l;
    li[l].next = be[to];
    be[to] = l;
    li[l].fr = to;
    li[l].to = fr;
    li[l].v = 0;
    li[l].c = -c;
    li[l].opt = l - 1;
  }
  void create()
  {
  }
  void clear()
  {
    l = s = t = 0;
    memset(be, 0, sizeof(be));
    memset(b, 0, sizeof(b));
  }
  bool spfa()
  {
    memset(dist, NCFZinf_, sizeof(dist));
    memset(b, 0, sizeof(b));
    dist[t] = 0;
    b[t] = 1;
    q.push_back(t);
    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] != NCFZinf;
  }
  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] && li[i].v && dist[to] == dist[now] - li[i].c)
      {
        int k = sap(to, min(maxf - tot, li[i].v));
        li[i].v -= k;
        li[li[i].opt].v += k;
        tot += k;
      }
    }
    return tot;
  }
  par query(int S, int T)
  {
    par ans;
    ans.a = ans.b = 0;
    s = S, t = T;
    while (spfa())
      while (int k = sap(s, NCFZinf))
      {
        memset(b, 0, sizeof(b));
        ans.a += k;
        ans.b += k * dist[s];
      }
    return ans;
  }
}zkw;
int m, n, e[60], s[60], t[60], tot, to_mem[60][60], S, T, to_pro[60], as[60][60], be[60], en[60], bel[60], ti[60][60];
int main()
{
  int k = 0;
    while (cin >> m >> n && m && n)
    {
        ++k;
        zkw.clear();
        memset(e, 0, sizeof(e));
        memset(s, 0, sizeof(s));
        memset(t, 0, sizeof(t));
        memset(as, -1, sizeof(as));
        memset(be, 0, sizeof(be));
        memset(en, 0, sizeof(en));
        memset(bel, 0, sizeof(bel));
        memset(to_pro, 0, sizeof(to_pro));
        memset(to_mem, 0, sizeof(to_mem));
        memset(ti, 0, sizeof(ti));
        S = 1, T = 2, tot = 2;
        for (int i = 0; i < m; ++i)
        {
            scanf("%d", &e[i]);
            for (int j = 0; j < n; ++j)
            {
                to_mem[i][j] = ++tot;
                TO[tot] = par(i, j);
                zkw.makeline(tot, T, 1, 0);
            }
        }
        for (int i = 0; i < n; ++i)
        {
            int p, now = ++tot;
            to_pro[i] = now;
            zkw.makeline(S, now, 1, 0);
            scanf("%d", &p);
            for (int j = 0; j < p; ++j)
                scanf("%d%d", &s[j], &t[j]);
            for (int j = 0; j < m; ++j)
            {
                if (e[j] < s[0]) continue;
                int va;
                for (int k = 0; k < p; ++k)
                    if (k == p - 1 || s[k + 1] > e[j])
                    {
                        va = t[k];
                        break;
                    }
                ti[i][j] = va;
                for (int k = 0; k < n; ++k)
                    zkw.makeline(now, to_mem[j][k], 1, (k + 1) * va);
            }
        }
        printf("%.2f\n", ((double)zkw.query(S, T).b) / n);
        for (int i = 0; i < n; ++i)
            for (int j = zkw.be[to_pro[i]]; j; j = zkw.li[j].next)
                if (!zkw.li[j].v)
                {
                    int to = zkw.li[j].to;
                    as[TO[to].a][TO[to].b] = i;
                    bel[i] = TO[to].a;
                    break;
                }
        for (int i = 0; i < m; ++i)
        {
            int tot = 0;
            for (int j = n - 1; j >= 0; --j)
                if (as[i][j] != -1)
                {
                    be[as[i][j]] = tot;
                    tot += ti[as[i][j]][i];
                    en[as[i][j]] = tot;
                }
        }
        for (int i = 0; i < n; ++i)
            printf("%d %d %d\n", bel[i] + 1, be[i], en[i]);
        printf("\n");
    }
}

BZOJ 1061: [Noi2008]志愿者招募

申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。经过估算,这个项目需要N 天才能完成,其中第i 天至少需要Ai 个人。 布布通过了解得知,一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天,招募费用是每人Ci 元。新官上任三把火,为了出色地完成自己的工作,布布希望用尽量少的费用招募足够的志愿者,但这并不是他的特长!于是布布找到了你,希望你帮他设计一种最优的招募方案。

noi08的题 好题啊~~
据说平均分12.x分= = 。。
这题
拿样例说吧(人工排序过了 = =)
3 3
1 2 2
2 3 4
2 3 5
3 3 2
设第k类找了x[k]个人
可以得
x[1] >= a[1]
x[1] + x[2] + x[3] >= a[2]
x[2] + x[3] + x[4] >= a[3]
把它们-y[i]化为等式 并移项

x[1] – y[1] – a[1] = 0
x[1] + x[2] + x[3] – y[2] – a[2]  = 0
x[2] + x[3] + x[4] – y[3] – a[3]  = 0

然后用后一个等式减前一个等式 并添加等式n+1
这是为了让每个变量都出现且仅两次 且一次为正 一次为负

x[1] – y[1] – a[1] = 0
x[2] + x[3] + y[1] – y[2] + a[1] – a[2] = 0
– x[1] + x[4] + y[2] – y[3] + a[2] – a[3] = 0
-x[2] – x[3] – x[4] + y[3] + a[3]  = 0

把这几个等式看成顶点
对于一个正的变量看成一个流入的流量
对于一个负的变量看成一个流出的流量
有关a的项为常数 可以看做从原点流入/流向汇点的流量

这样就出现了一个建图:
如果等式u包含变量x[i] 等式v包含变量-x[i] 则从v向u连一条边 容量inf
对于y同理
如果等式u包含a的项的和k为正数则从原点连向u一条边 容量为k
否则连向汇点一条边 容量为-k

又我们要求的是最小费用 x[i]每多1 则ans多v[i]
可以把对于x的连边加上费用 为v[i]
求最小费用流即为ans

—————–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 ll maxn = 1010;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
ll dist[maxn], b[maxn], n, m, l, be[maxn], s, t;
struct line
{
    ll next, to, v, c, opt;
    line(ll f = 0, ll t = 0, ll va = 0, ll co = 0, ll op = 0)
    : next(be[f]), to(t), v(va), c(co), opt(op) {}
}li[1000000];
deque<ll> q;
void makeline(ll fr, ll to, ll v, ll c)
{
    ++l;
    li[l] = line(fr, to, v, c, l + 1);
    be[fr] = l;
    ++l;
    li[l] = line(to, fr, 0, -c, l – 1);
    be[to] = l;
}
ll spfa()
{
    memset(b, 0, sizeof(b));
    memset(dist, 0x3f, sizeof(dist));
    q.push_front(t);
    dist[t] = 0;
    b[t] = 1;
    while (!q.empty())
    {
        ll now = q.front();
        q.pop_front();
        for (ll i = be[now]; i; i = li[i].next)
        {
            ll 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[q.front()] > dist[to]) q.push_front(to);
                else q.push_back(to);
            }
        }
        b[now] = 0;
    }
    return dist[s];
}
ll sap(ll now, ll maxf)
{
    if (now == t) return maxf;
    ll tot = 0;
    b[now] = 1;
    for (ll i = be[now]; i; i = li[i].next)
    {
        ll to = li[i].to;
        if (!b[to] && li[i].v && dist[to] == dist[now] – li[i].c)
        {
            ll t = sap(to, min(maxf – tot, li[i].v));
            li[i].v -= t;
            li[li[i].opt].v += t;
            tot += t;
            if (tot == maxf) return tot;
        }
    }
    return tot;
}
ll ZKW_CF()
{
    ll ans = 0, m;
    while (spfa() != inf)
        while (m = sap(s, inf))
        {
            memset(b, 0, sizeof(b));
            ans += m * dist[s];
        }
    return ans;
}
int main()
{
    scanf(“%lld%lld”, &n, &m);
    s = 0;
    t = n + 2;
    ll la = 0;
    for (ll i = 1; i <= n + 1; i++)
    {
        ll p;
        if (i == n + 1) p = 0;
        else
        {
            scanf(“%lld”, &p);
            makeline(i, i + 1, inf, 0);
        }
        if (-p + la > 0) makeline(s, i, -p + la, 0);
        else makeline(i, t, -la + p, 0);
        la = p;
    }
    for (ll i = 0; i < m; i++)
    {
        ll fr, to, v;
        scanf(“%lld%lld%lld”, &fr, &to, &v);
        makeline(to + 1, fr, inf, v);
    }
    printf(“%lld”, ZKW_CF());
}

BZOJ 1070: [SCOI2007]修车

同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。 说明:顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

这…
不是noi那题吗 – –
我是先A了这题 感觉好像在哪看过
好像是noi?
然后 去看了下。。
还真是
呵呵。。
想当年~
真沙茶= =

一个技术员拆成n个 向汇点连边 费用0 容量1
每个车主从原点连边 费用0 容量1
每个车主i向每个技术员j的每个点k 连边 费用v[i][j] * k 容量1

然后ans/n就是平均(毫无意义?= =)

————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;
const int inf = 0x7f7f7f7f;
int be[maxn], l, n, m, v[maxn][maxn], s, t, tot, to[maxn][maxn], dist[maxn], b[maxn];
struct line
{
  int next, to, v, c, opt;
  line(int f = 0, int t = 0, int va = 0, int co = 0, int op = 0)
  : next(be[f]), to(t), v(va), c(co), opt(op){}
}li[1000005];
deque<int> q;
void makeline(int fr, int to, int v, int co)
{
  ++l;
  li[l] = line(fr, to, v, co, l + 1);
  be[fr] = l;
  ++l;
  li[l] = line(to, fr, 0, -co, l – 1);
  be[to] = l;
}
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];
}
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;
}
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;
}
int main()
{
  scanf(“%d %d”, &m, &n);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) scanf(“%d”, &v[i][j]);
  s = 0;
  t = 1;
  tot = 1;
  for (int i = 0; i < m; i++)
    for (int j = 1; j <= n; j++)
    {
      to[i][j] = ++ tot;
      makeline(to[i][j], t, 1, 0);
    }
  for (int i = 0; i < n; i++)
  {
    int now = ++ tot;
    makeline(s, now, 1, 0);
    for (int j = 0; j < m; j++)
      for (int k = 1; k <= n; k++)
        makeline(now, to[j][k], 1, v[i][j] * k);
  }
  printf(“%.2f”, ((double)ZKW_CF()) / n);
}

BZOJ 2756: [SCOI2012]奇怪的游戏

Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N*M 的棋盘上玩,每个格子有一个数。每次 Blinker 会选择两个相邻
的格子,并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数,如果永远不能变成同
一个数则输出-1。

对棋盘进行黑白染色
设黑格个数为num1 数值和为sum1
设白格个数为num1 数值和为sum1

设最后都变为x

num1 * x – sum1 = num2 * x – sum2
x = (sum1 – sum2) / (num1 – num2)
当num1 ≠ num2时 可以解出 x 再用网络流check即可

对于num1 = num2时 可以发现 对于一个合法的x k>=x都是一个合法的解
因为num1 = num2 => (num1 + num2) % 2 == 0 可以构造一层的满覆盖
所以可以二分x 然后用网络流check

建图:
如果点k为白
建边(s, k, x – v[k])
如果为黑
建边(k, t, x – v[k])
对相邻点u、v (u为白)
建边 (u, v, inf)

———————–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 = 1610;
const ll inf=(1LL)<<50;
int be[maxn], s, t, n, m, p, to[50][50], l, d[maxn], note[maxn];
ll v[50][50];
struct line
{
  int next, to, opt;
  ll v;
  line(int f = 0, int t = 0, ll va = 0, int op = 0)
  : next(be[f]), to(t), v(va), opt(op) {}
}li[100005];
void clear()
{
  memset(be, 0, sizeof(be));
  memset(d, 0, sizeof(d));
  memset(note, 0, sizeof(note));
  l = 0;
}
ll sap(int now, ll maxf)
{
  if (now == t) return maxf;
  ll tot = 0;
  int mi = p + 1;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (li[i].v && d[to] + 1 == d[now])
    {
      ll t = sap(to, min(maxf – tot, li[i].v));
      li[i].v -= t;
      li[li[i].opt].v += t;
      tot += t;
      if (tot == maxf || d[s] >= p + 1) return tot;
    }
    if (li[i].v && mi > d[to]) mi = d[to];
  }
  if (!tot)
  {
    if (!–note[d[now]])
    {
      d[s] = p + 1;
      return 0;
    }
    ++note[d[now] = mi + 1];
  }
  return tot;
}
inline void makeline(int fr, int to, ll v)
{
  ++l;
  li[l] = line(fr, to, v, l + 1);
  be[fr] = l;
  ++l;
  li[l] = line(to, fr, 0, l – 1);
  be[to] = l;
}
inline bool check(ll top)
{
  clear();
  ll tp = 0;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    {
      if ((i + j) & 1) makeline(to[i][j], t, top – v[i][j]);
      else
      {
        makeline(s, to[i][j], top – v[i][j]);
        if (i) makeline(to[i][j], to[i – 1][j], inf);
        if (j) makeline(to[i][j], to[i][j – 1], inf);
        if (i < n – 1) makeline(to[i][j], to[i + 1][j], inf);
        if (j < m – 1) makeline(to[i][j], to[i][j + 1], inf);
        tp += top – v[i][j];
      }
    }
  note[0] = p + 1;
  ll ans = 0;
  while (d[s] < p + 1)
    ans += sap(s, inf);
  return ans == tp;
}
int main()
{
  int test;
  scanf(“%d”, &test);
  while (test–)
  {
    clear();
    scanf(“%d%d”, &n, &m);
    s = 0;
    t = 1;
    p = 1;
    ll mi = 0;
    ll sum1 = 0;
    ll sum2 = 0;
    int num1 = 0;
    int num2 = 0;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++)
        {
          scanf(“%lld”, &v[i][j]);
          if ((i + j) & 1) num1++, sum1 += v[i][j];
          else num2++, sum2 += v[i][j];
          if (v[i][j] > mi) mi = v[i][j];
          to[i][j] = ++ p;
        }
    if (num1 != num2)
    {
      if (abs(sum1 – sum2) % abs(num1 – num2))
      {
        printf(“-1\n”);
        continue;
      }
      ll x = abs(sum1 – sum2) / abs(num1 – num2);
      if (x < mi || !check(x))
      {
        printf(“-1\n”);
        continue;
      }
      else
      {
        ll r = x;
        ll ans = 0;
        for (int i = 0; i < n; i++)
          for (int j = 0; j < m; j++)
            ans += r – v[i][j];
        printf(“%lld\n”, ans / 2);
      }
      continue;
    }
    if (sum1 != sum2)
    {
      printf(“-1\n”);
      continue;
    }
    ll l = mi – 1;
    ll r = inf;
    while (l + 1 < r)
    {
      ll mid = (l + r) / 2;
      if (check(mid)) r = mid;
      else l = mid;
    }
    if (r == inf) printf(“-1\n”);
    else
    {
      ll ans = 0;
      for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
          ans += r – v[i][j];
      printf(“%lld\n”, ans / 2);
    }
  }

}

网络流小结②

负权环的处理。。
这是个比较蛋疼的东西。。
其实也不是很蛋疼。。
不过。。
按队长的话说。。
如果你建的图出现负环 那一般就是你建错图了 或可以避免。。
但是那是一般。。
so。。
而且处理负环的这个思想十分的重要。。
这几天我唯一没有想出来的(其他题 至少网络流的部分想出来了。。)就是这个思想。。
其实也不叫思想吧。。
网络流的性质啊。。
noi2008 志愿者招募。。
流量平衡。。
呵呵。。
呵。。
。。

好吧不蛋疼了- –
处理负环的思想就是先把负权边满流 类似上下界流处理下界 不同的是这个在流后要加反向容量
这样会有一些点不满足流量平衡 设vi = 流入点i流量-点i流出流量为

然后建一个超级源 对所有vi>0的点连边 容量为vi
建一个超级汇 对所有vi<0的点连边 容量为-vi
以超级源为源 以超级汇为汇 跑一次最大流 然后剩余网络就是满足没有负费用环的图
直接跑费用流即可
这个操作称为退流

另外退流还可以解决有上下界的网络流问题
对于一条边有上下界的边 改为只有上界 为原上界-下界
建超级源汇的操作一样
称这个新网络为附加网络

① 有源汇的上下界最大流
1.构造附加网络

     2.对ss、tt求最大流(ss、tt满流则有解)
     3.若有解,对s、t求最大流 即为ans
② 有源汇的上下界最小流
1.构造附加网络
2.加边(t, s, inf)
3.对ss、tt求最大流
4.满流即有解 解为t, s边的流量
③ 无源汇的上下界最大最小流

最大:
1.构造附加网络
2.加边(t, s, l, inf)(是有上下界的边)
3.二分l
4.用最大流是否满流判断是否有解

最小:
更最小差不多 就是把加边改成(t, s, 0, r) 然后二分r 判定

———————————–
一共A了6、7题还是多少的 题解放在下篇

网络流小结①

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

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

 

网络流(三)–最大流题解(3)

Farmer John重新建设了他的农庄,将其建成一个个农舍。每个农舍只能住一只奶牛,当然,

每只奶牛只能住一间农舍。而基于居住环境的不同,对一只奶牛而言,当且仅当它居住在某些农舍时,
才会产奶。现给定每个农庄可以令那些奶牛产奶,问在最合适的分配下,会产奶的奶牛最多有几只。
——————————————————————————————————————–
这个构图就so显然了 从源点向每个牛连一条容量为1的边
从每个农舍向汇点连一条容量为1的边
如果牛i喜欢农舍j  就连边i->j 容量为1
——————————————————————————————————————–
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
struct line
{
  int to, v, opt, next;
};
const int maxn = 1000;
line a[100000];
int dinic[maxn], note[maxn], be[maxn], l, n, s, t;
void makeline(int f, int t, int v, int opt)
{
  l++;
  a[l].next = be[f];
  be[f] = l;
  a[l].to = t;
  a[l].v = v;
  a[l].opt = opt;
}
int min(int a, int b)
{
  if (a > b) return b;
  else return a;
}
int sap(int now, int maxf)
{
  if (now == t) return maxf;
  int i = be[now];
  int sum = 0;
  int minn = n;
  while (i != 0)
  {
    if (dinic[a[i].to]+1 == dinic[now] && a[i].v > 0)
    {
      int d = sap(a[i].to, min(maxf-sum, a[i].v));
      sum += d;
      a[i].v -= d;
      a[a[i].opt].v += d;
      if (sum == maxf || dinic[s] >= n) return sum;
    }
    if (a[i].v > 0) minn = min(minn, dinic[a[i].to]);
    i = a[i].next;
  }
  if (sum == 0)
  {
    note[dinic[now]]–;
    if (note[dinic[now]] == 0)
    {
      dinic[s] = n;
      return 0;
    }
    dinic[now] = minn+1;
    note[dinic[now]]++;
  }
  return sum;
}
int main()
{
  freopen(“poj1274.in”,”r”,stdin);
  freopen(“poj1274.out”,”w”,stdout);
  while (cin >>n)
  {
    memset(dinic, 0, sizeof(dinic));
    memset(a, 0, sizeof(a));
    memset(note, 0, sizeof(note));
    memset(be, 0, sizeof(be));
    l = 0;
    s = 0;
    t = 800;
    int m;
    cin >> m;
    for (int i = 1; i <= n; i++)
    {
      makeline(s, i, 1, l+2);
      makeline(i, s, 0, l);
    }
    for (int i = 1; i <= m; i++)
    {
      makeline(i+n, t, 1, l+2);
      makeline(t, i+n, 0, l);
    }
    for (int i = 1; i <= n; i++)
    {
      int k;
      scanf(“%d”, &k);
      for (int j = 1; j <= k; j++)
      {
        int num;
        scanf(“%d”, &num);
        makeline(i, num+n, 1, l+2);
        makeline(num+n, i, 0, l);
      }
    }
    n += m+2;
    note[s] = n;
    int ans = 0;
    while (dinic[s] < n) ans += sap(s, 1000);
    printf(“%d\n”, ans);
  }
  fclose(stdin);fclose(stdout);
}
——————————————————————————————————————–
这题是用网络流解决二分图匹配的问题
虽然这题so easy
但还是挺经典的题型和建图
故提之·~

网络流<三>–最大流题解(2)

给出一些挤奶机、奶牛,以及他们之间距离,每只奶牛都要走到任意一台机器中,每台机器最多为M只奶牛服务,问所有奶牛都完成任务,所走的路程最远的那只奶牛,所走的路程最短可以是多少。(这里注意给出的不一定是最短路径,0代表的是两点之间没有直接路径。)

继续阅读

网络流<三>–最大流题解(1)

 

《POJ 1149  PIGS》

【题目大意】

有 M 个猪圈,每个猪圈里初始时有若干头猪。一开始所有猪圈都是关闭的。依
次来了 N 个顾客,每个顾客分别会打开指定的几个猪圈,从中买若干头猪。每
个顾客分别都有他能够买的数量的上限。每个顾客走后,他打开的那些猪圈中的
 
猪,都可以被任意地调换到其它开着的猪圈里,然后所有猪圈重新关上。问总共
最多能卖出多少头猪。 (1 <= N <= 100, 1 <= M <= 1000)
 
举个例子来说。有3个猪圈,初始时分别有3、 1和 10头猪。依次来了 3个顾客,
第一个打开1号和 2 号猪圈,最多买 2头;第二个打开 1号和3 号猪圈,最多买
3头;第三个打开 2号猪圈,最多买 6头。那么,最好的可能性之一就是第一个
顾客从 1 号圈买 2 头,然后把 1 号圈剩下的 1 头放到 2 号圈;第二个顾客从 3
号圈买 3头;第三个顾客从 2号圈买2头。总共卖出 2+3+2=7头。
———————————————————————————————————-
 
 
先用最朴素的建流  对于每一个时间的每个猪圈建立点  共n*m个  对每个顾客也
建点  向会点连边  容量为该顾客购买量   每个从源点向第一个时间的每个猪圈连
边  容量为每个猪圈初始猪数  对于每个时间的、有被该时间的顾客开过的猪圈
向这个顾客连一条边 容量无限  并连向下一个时间的所有在现在被开的猪圈
如: d(i,j)表示第i个时间的第j个猪圈   则如果第3个顾客 开了1 3 4猪圈 就连边
(3,1)->(4,1)   (3,1)->(4,3)    (3,1)->(4,4)
(3,3)->(4,1)   (3,3)->(4,3)    (3,3)->(4,4)
(3,4)->(4,1)   (3,4)->(4,3)    (3,4)->(4,4)
表示他打开的那些猪圈中的猪,都可以被任意地调换到其它开着的猪圈里

构图如图psb (2)显然这个构图的点略多。。。。so有一堆优化

 

规律 1.  如果几个结点的流量的来源完全相同,则可以把它们合并成一个。

规律 2.  如果几个结点的流量的去向完全相同,则可以把它们合并成一个。

规律 3.  如果从点 u 到点 v 有一条容量为∞的边,并且点 v 除了点 u 以外没有别的流量来源,则可以

把这两个结点合并成一个。

然后。。这个图就边成了。:psb (4)

 

然后构图变成:

每个顾客分别用一个结点来表示。

对于每个猪圈的第一个顾客,从源点向他连一条边,容量就是该猪圈里的

猪的初始数量。如果从源点到一名顾客有多条边,则可以把它们合并成一

条,容量相加。

对于每个猪圈,假设有 n个顾客打开过它,则对所有整数 i∈[1, n),从该

猪圈的第i 个顾客向第 i + 1个顾客连一条边,容量为∞。

从各个顾客到汇点各有一条边,容量是各个顾客能买的数量上限。

 

——————————————————————————————————————–

 

#include <iostream>

using namespace std;

struct line

{

int v,next,to,opt;

};

int n,m,be[100005],c[100005],dinic[100005],note[100005];

line a[100005];

int l=0;

void makeline(int from,int to,int v,int opt)

{

l++;

a[l].next=be[from];

be[from]=l;

a[l].v=v;

a[l].opt=opt;

a[l].to=to;

}

int min(int a,int b)

{

if (a>b) return b;else return a;

}

int maxflow(int now,int maxf)

{

if (now==n-1) return maxf;

int i=be[now];

int sum=0;

int minn=n;

while (i!=0)

{

if (dinic[a[i].to]+1==dinic[now] && a[i].v>0)

{

int d=maxflow(a[i].to,min(maxf-sum,a[i].v));

sum+=d;

a[i].v-=d;

a[a[i].opt].v+=d;

if (sum==maxf || dinic[0]>=n) return sum;

}

if (a[i].v>0) minn=min(minn,dinic[a[i].to]);

i=a[i].next;

}

if (sum==0)

{

note[dinic[now]]–;

if (note[dinic[now]]==0)

{

dinic[0]=n;

return 0;

}

dinic[now]=minn+1;

note[dinic[now]]++;

}

return sum;

}

int main()

{

freopen(“poj1149.in”,”r”,stdin);

freopen(“poj1149.out”,”w”,stdout);

cin>>m>>n;

int b[100005];

for (int i=1;i<=m;i++)

{

cin>>c[i];

b[i]=0;

}

for (int i=1;i<=n;i++)

{

int k;

cin>>k;

for (int j=1;j<=k;j++)

{

int s;

cin>>s;

if (b[s]==0)

{

makeline(0,i,c[s],l+2);

makeline(i,0,0,l);

b[s]=i;

}

else

{

makeline(b[s],i,999999,l+2);

makeline(i,b[s],0,l);

b[s]=i;

}

}

cin>>k;

makeline(i,n+1,k,l+2);

makeline(n+1,i,0,l);

}

n=n+2;

note[0]=n;

int ans=0;

while (dinic[0]<n) ans+=maxflow(0,1000000);

cout<<ans;

fclose(stdin);fclose(stdout);

}

——————————————————————————————————————–
网络流的构图其实直接怎么有坑怎么构图、、不用考虑时间什么什么的
能建出图就很好了  大不了再优化之~~其实我做了好几题网络流  基本没
有一题是专门卡你构图的  = =so…