网络流24题

题记:

看上去机房的dalao们都早就攻克了网络流,所以我也写了一些的题解以此来记录这些东西!

但是有一些题目由于是模板,而且网上真的有好多厉害的博客,就稍微讲的少了一点!请见谅!

继续阅读 网络流24题

飞行员配对方案问题

裸的一个二分图的模板!

如果有不懂的可以上百度去搜索一下:

u=2543358439,2520347586&fm=58&bpow=600&bpoh=600.jpg

其实博主之前也是看这位的博客的,挺好的,但是少了一点总结:传送门

个人觉得其实二分图的精髓就是一个贪心,对于当前的节点,看看之前的点能不能腾出一个“位置”让这个节点能够有二分图匹配!那么依照这个性质,我们可以干很多事情啦!

代码:

代码

分块–优美的暴力

分块

其实就是相当于分治的思想  对于每一块分别进行维护从而达到降低复杂度的效果

其实就像这样:对于这几个独立的区域分别进行询问或修改,最后累加成答案

草图

确定块大小

先将块的大小设置成k 多为:捕获

我们可以先算出每一个操作的复杂度进行分析,然后捕获.PNG我们会得到一个多项式(含k的式子),求其最小值,于是我们有这几种方法:

1.基本不等式

捕获
基本不等式

2.图像法(GeoGebra)

捕获.PNG
GeoGebra

 

3.求导

想必大家都很熟悉了!就不一一赘述了!

基本操作:

其实就是这样:

块.png
对于区间覆盖的块打个标记,两边未完全覆盖的块直接暴力修改(询问)

闲话不多说,我们直接开始讲题目就好了!

T1:教主的魔法

题意简化:

支持2种操作:

  1. M  : 区间询问[l,r]中元素大于 C 的个数 C变值
  2. A  : 区间将[l,r]中的每一个元素加上 w, w变值

样例:

input:

5 3

1 2 3 4 5

A 1 5 4

M 3 5 1

A 1 5 4

ouput:

2

3

分析:

我们将每一个块内的元素分别进行排序,对于某个询问数字 x  只要二分一下位置就好了!

修改:

对于边界的情况暴力处理直接把元素加上 w,

整个块的话就标记一个 addmark[ ] 来表示区间加上了多少

询问

边界情况就直接 for 一遍

整块的话就可以二分 x + addmark[i] 的位置,对答案产生贡献就好了!

代码:

代码

T2:[HNOI2010]弹飞绵羊

题意:

有一个a序列:对于位置i,可以跳到i + a[i] 的位置

我们认为出界就是i 跳跃之后的位置超过了序列长度n

支持2种操作:

  1. 询问 位置i的跳出界的次数!
  2. 单点修改a[i]的权值

样例:

input:

4
1 2 1 1
3
1 1
2 1 1
1 1

output:

2

3

分析:

我们可以将序列分成捕获段,每一段的点储存信息:

  1. 跳出该块的跳跃次数
  2. 跳出该块之后的位置

那么我们对于每一个询问就可以 sqrt(n) 的时间内计算贡献

而且我们修改时只需要对于一个长度为根号n的块金星秀高就好了,那么我们的复杂度就是

捕获

代码:

代码

分块小结论:

1.我们对于询问区间大于(小于)某一个数的问题可以直接用分块,对于每一个块进行排序来解决问题

2.其实每一个问题都是优化而来的,我们发现其实想T2一样,其实我们可以O(1)询问答案,O(n)修改值的,但是就是这样会TLE,询问复杂度太大了,那么我们就可以将分块来介入,就像将这个O(n)的修改简化为O(sqrt(n))复杂度的式子来计算,但是询问的复杂度升高,也变成根号的,那么平均一下就可以解决了!这就是我所理解的分块:

对于问题规模缩小化,将询问与修改的复杂度进行平均来达到效果!

 

 

mcmf

费用流

做法

  1. 在残余网络上寻找最短路
  2. 对该路径进行增广, 对答案产生贡献
  3. 不断重复opt.1操作, 直至s\to t不存在路径

证明

定义

  1. 定义f作为图中的流

  2. f\text{-}g表示流f与流g之间不同的流量

  3. in(u)表示u的入流, out(u)表示u的出流

Proof 1

  • f是最小费用流 \Leftrightarrow 残余网络中无负圈

假设, 存在费用比f更小的流f’.

观察二者, 由于流量相同, 那么out(s), in(t)均相同

\forall u, in(u)=out(u)f, f’中恒成立.

于是f’\text{-}f形成的流是由若干圈组成的!

因为cost(f’) < cost(f)f 的残留网络中存在至少一个负圈.

Proof 2

  • 利用数学归纳证明

假设f_i 表示流量为i的最小费用流

f_0便是原图(显然原图中不存在负圈).

那么根据我们的做法, 得到了f_{i+1}, 那么假设存在费用更小的流f_{i+1}’

f_{i + 1} \text{-}f_i是一条s\to t最短路, 而f_{i+1}’\text{-}f_i是一条s\to t的路径与若干圈组成的

那么这些圈中则必定存在负圈, 这与f_i是最小费用流相悖.

故上述成立.


原始对偶算法

不要在意名字

背景: 图中存在负权边, spfa已经死了

思考: 求最短路可否用Dijkstra呢?

假如我们给每一个节点 附上 h(i):使得e(u,v)’ = e(u,v) + h(u) – h(v)

且它恒非负, 那就可以用\text{Dijkstra}

  • 考虑最短路的性质: dis(u) + e(u, v) \geq dis(v)

得到dis(u)-dis(v) + e(u, v) \geq 0

那么我们将dis(u)-dis(v) + e(u, v)作为新的边权, 记为e(u,v)’

不难证明以它为新图所得到的最短路与原图的最短路经过路径是一样的.

那么这样就意味着我们可以\text{Dijkstra}了. (比spfa不知道高到哪里去了, 雾

即: 在跑no.i次增广的时候的势h_i(u)dis_i(u)

等等, 如果我们已经知道了势(即最短路), 那还tm要增广干嘛

于是发现其实h_i(u)=h_{i-1}(u)也是可以的, 即变成上次增广的原图u的最短路.

从简证明:

  1. 若e(u,v)在no.i-1次增广时存在, 那么显然满足

  2. 若e(u,v)在no.i-1次增广不存在

    那么此次它的出现是因为增广导致的

    意思就是说它一定在上次的s\to t的最短路上, 那么e(u, v) = -e(v, u) = 0

    依旧非负.

%:pragma GCC optimize("Ofast", 2)
#include <bits/stdc++.h>
using namespace std;

namespace {
    inline void read(int &x) {
        x = 0; int f = 1; char c = getchar();
        for(; !isdigit(c); c = getchar())
            if(c == '-') f = -1;
        for(;  isdigit(c); c = getchar())
            x = (x << 3) + (x << 1) + (c ^ '0');
        x *= f;
    }
}

const int N = 5e3 + 5, M = 5e4 + 5;
const int inf = 1e9;

# define pi pair<int, int>

int n, m, s, t, u, v, c, w;

namespace Primal {
    int Ecnt = 1, first[N], nex[M * 2], arr[M * 2], cap[M * 2], cost[M * 2];
    int dis[N], h[N], pree[N], prev[N], F, C;

    template <typename T>
    inline void Min(T &a, T b) {
        if(a > b) a = b;
    }
    inline void Ad(int u, int v, int c, int w) {
        nex[++Ecnt] = first[u], first[u] = Ecnt, arr[Ecnt] = v, cap[Ecnt] = c, cost[Ecnt] = w;
    }
    inline void add(int u, int v, int c, int w) {
        Ad(u, v, c, w), Ad(v, u, 0, -w);
    }
    void Dijkstra() {
        static priority_queue<pi, vector<pi>, greater<pi> > q;
      for(; !q.empty(); q.pop());
        fill(dis, dis + 1 + n, -1);
        dis[s] = 0, q.push(pi(0, s));
        // printf("-----------\n");
        while(!q.empty()) {
            pi now = q.top(); q.pop();
            int u = now.second;
            if(dis[u] < now.first) continue;
            for(int i = first[u]; i; i = nex[i]) {
                static int v; v = arr[i];
                if(!cap[i]) continue;
                if(dis[v] < 0 || dis[v] > dis[u] + cost[i] + h[u] - h[v]) {
                    dis[v] = dis[u] + cost[i] + h[u] - h[v];
                    prev[v] = u, pree[v] = i;
                    q.push(pi(dis[v], v));
                }
            }
        }
    }
    pi solve(int s, int t) {
        fill(h, h + 1 + n, 0);
        for(int f = inf; f > 0; ) {
            Dijkstra();
            if(dis[t] < 0) break;
            for(register int i = 1; i <= n; ++i) // be careful this for
                h[i] += (dis[i] != -1) ? dis[i] : 0;
            int d = f;
            for(int u = t; u != s; u = prev[u]) 
                Min(d, cap[pree[u]]);
            f -= d, F += d, C += h[t] * d;
            assert(C >= 0);
            for(int u = t; u != s; u = prev[u]) {
                cap[pree[u]] -= d;
                cap[pree[u] ^ 1] += d;
            }
        } return pi(F, C);
    }
}
using namespace Primal;

int main() {
    read(n), read(m), read(s), read(t);
    for(int i = 1; i <= m; ++i) {
        read(u), read(v), read(c), read(w);
        add(u, v, c, w);
    }
    pi get = solve(s, t);
    printf("%d %d\n", get.first, get.second);
    return 0;
}

其实大家可能最疑惑的就是为什么有代码是 :

   for(int i = 1; i <= n; ++i) h[i] += dist[i];

从理论出发, h'(i)此时定义为no.(i-1)次增广时原图中的最短路 (再次强调是原图!)

而数组dist实际存储的是

\begin{aligned} \text{dist[u]}&=\sum e'(u, v) \\ &=\sum \bigg( h(u)-h(v) + e(u, v) \bigg) \\ &= dis(u) + h(s)-h(u) \\ &= dis(u) – h(u) \\ \end{aligned}

那么h'(u) = dis(u) = h(u) + dist[u]​

所以就是 一直都是 “+=”

Codeforces960F – Pathwalks + 最长不下降子序列(LIS)选讲

首先先来吐槽一下这场比赛,简直就是我第一次要么 WA 1 或者就是 WA 35+ 的一场比赛,也不知道出题人怎么这么流比

LIS

LIS 背景:

 给你一个序列 a 让你选出最长的子序列,使得每一个元素满足捕获

样例

input: 7 2 5 3 4 1 7 6

output: 4 (注释: 选择 2 3 4 6)

考虑最朴素的 捕获.PNG 做法,其实就是我们设为捕获.PNG

 于是我们有了DP方程:

捕获.PNG

 但是很容易想到我们也可以二分找出答案对吧!

于是捕获算法奉上:

代码

Codeforces 960F 

题意:

有一张有向图,按照顺序输入,让你求连续的一条路径,使得边的输入顺序递增而且权值也是递增的,输出路径的长度! !

20180409191948647.png

 分析:

此题我们可以快速想到一个复杂度较大的DP方程(所有算法都是优化而来的嘛)

我们用f[i][j] 表示 i 节点结尾的路径最长的边权值不超过 j 的答案

 每一次输入一条有向边 u->v 权值为 w

都有 

捕获

同理依次更新 f[v][w – 1e5]

但是我们会发现和LIS 其实非常的像对吧,于是我们f 数组用map来维护一下就好了

代码