DEL 发布的文章

雅礼集训

3.23

题目都很简单,AK不难。T1 T3 很快想到正解,但一直在犹豫。

其实没什么好犹豫的,但总觉得正解有比我妙的思路。……反正想到了满分做法就上就行了的……

省下时间刚 T2 或许就做出来了。

卷积时快速幂的因子优化的想法也真的很妙,没想出来。

对指数使用牛顿级数后预处理……是做了多少题才这么熟练啊……

推式子能力很差再一次被证实。接下来要好好思考牛顿级数的应用。

难题选讲#1讲了异或前缀和的结论。虽然好像挺没营养的,但是很有趣!n,1,n+1,0 分别对应模为 0,1,2,3 的情况。(总感觉我以前见过这个结论……说不定我还证过的……老了老了)

2 还是很变态的计数题的。

考虑

3 两道推式子的概率题。不难。让我想可能得想好一会。

3.31

下午比赛。精神不是很好。

T1 一道期望题。开始以为是计数问题,分析出来了各变量间不独立……就不会做了……根本没想到枚举操作的子集。WHJ 用子集卷积的思路想到了解法,还是稳的。

T2 一道很好的分治题。暴力 $ \mathcal O(n^2) $ 有 60+' 。最后不够时间,才打了三次方的骗分……

T3 一直在考虑怎么设计信息和合并信息……结果重新定义矩阵作为信息……因为满足结合律套用矩乘快速幂并且线段树维护即可……讲课强调了那么多次要把储存的信息单独拉出来考虑分析性质,自己却在划水……然后树剖操作一发再维护些信息。

总的来说如果对期望的枚举子集的概念和技术再熟悉一点的话就可以做出 T1 了。T2 没去打满暴力很可惜。T3 信息状态的设计真的很妙。给自己提了个大醒。

能力本当得分 100+62+65=227 . 这是 rk#4 了.

难题选讲。1 的字符串处理挺妙的。2 是whj,多项式的构造或分治也值得学一学。3 是两道涉及平方的计数题,都不会,技巧很值得了解。 4 是置换和群论好题,很牛逼的,可以说是很神仙了,反正我不去学。

链的剖分及分治

重链剖分

从一个点到根经过的轻链数量级为 $ O(\lg n) $.

启发式合并(链分治)

统计树上具有某一种特征(颜色)的结点数。

两种方法:平衡树启发式合并、树链剖分启发式合并。

前者是对每个结点维护一个平衡树,然后在父亲处保留最大的孩子,其他孩子暴力合并到其上,复杂度 $ O(n \lg^2 n) $. 使用 splay 可以把平方去掉,但这怕是数据结构学傻。

后者保留重孩子信息,对轻孩子直接暴力统计。

看起来复杂度迷迷的?实际上插入集合是 $O(1)$ 的,清空集合是均摊 $ O(1) $ 的;只有遇到轻边,这棵子树才会被遍历,用轻重链性质知道一个点到根最多只有 $ O(\lg n) $ 条轻边,总的复杂度也是 $ O(n \lg n) $。跑得飞快。

事实上和点分思路很像。

只是处理的对象是有根树的时候,不能用点分,用数据结构又麻烦,这个时候就是启发式合并的时间了。

即便是无根树,也可以用启发式合并。

其实这个东西就是链分治?

Ex.

给定一棵有根树,结点带颜色。问某一棵子树颜色为 $k$ 的结点的数量。

Sol.

记录每个结点子树的颜色信息。

若是重孩子则被父亲继承,否则舍弃,在父亲处暴力统计余下子树。

CF 600E

给一棵有根树,结点带颜色。问每一棵子树出现最多的颜色的编号和。 $ n\le 2\times10^5 $.

Sol.

与上例思路一致。

插入集合显然可以做到 $ O(1) $.

Code (93, 11400)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e5 + 10;
struct E{int v, n; }e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v){e[ec] = (E){v, h[u]}; h[u] = ec++;}
int c[maxn], size[maxn], hson[maxn];
void getsize(int u = 1, int f = 0)
{
    size[u] = 1, hson[u] = 0;
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
        getsize(v, u), size[u] += size[v], hson[u] = (size[v] > size[hson[u]] ? v : hson[u]);
}
long long sum = 0, maxc = 0, cnt[maxn]; bool tag[maxn];
void dfs2(int u, int f, int k)
{
    cnt[c[u]] += k;
    if(k > 0 && cnt[c[u]] >= maxc)
    {
        if(cnt[c[u]] > maxc) sum = 0, maxc = cnt[c[u]];
        sum += c[u];
    }
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f && !tag[v])
        dfs2(v, u, k);
}
long long ans[maxn];
void dfs(int u = 1, int f = 0, bool k = false)
{
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f && v != hson[u])
        dfs(v, u);
    if(hson[u]) dfs(hson[u], u, true), tag[hson[u]] = true;
    dfs2(u, f, 1);
    ans[u] = sum;
    if(hson[u]) tag[hson[u]] = false;
    if(!k) dfs2(u, f, -1), maxc = sum = 0;
}
int main()
{
    int n; read(n);
    for(int i = 1; i <= n; ++i) read(c[i]);
    for(int i = 1, u, v; i < n; ++i) read(u, v), add_edge(u, v), add_edge(v, u);
    getsize();
    dfs();
    for(int i = 1; i <= n; ++i) printf("%I64d ", ans[i]);
    return 0;
}

CF 741D

给一棵树。边上有字母 a~v 。求最长的路径,使得边上字母重排后可以构成回文串。

Sol.

首先将字母视为对应二进制上的某一位,那么能构成回文串等价于将边的数异或起来为零或二的幂。

那我们改为储存每个点到某一个定点的权值异或和。

点分的动机应该很自然。

现在就是要在不同子树中求两个点,使得他们的权值异或和为零或二的幂,且深度和最大。

然后这是非常简单的问题了。

再注意到根本不需要点分,重链启发式合并就可以了。

Code (1263, 73000)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 5e5 + 10, sigma = 22, maxm = 1 << sigma, INF = 0x3f3f3f3f;
struct E{int v, n, w; } e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v, int w){e[ec] = (E){v, h[u], w}; h[u] = ec++;}
int w[maxn], size[maxn], hson[maxn], dep[maxn];
void getsize(int u = 1)
{
    size[u] = 1, hson[u] = 0;
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v)
        w[v] = w[u] ^ (e[i].w), dep[v] = dep[u] + 1, getsize(v), size[u] += size[v], hson[u] = (size[v] > size[hson[u]] ? v : hson[u]);
}
int maxc = 0, maxdep[maxm], cdep;
inline void update(int u)
{
    maxc = max(maxc, maxdep[w[u]] + dep[u] - 2 * cdep);
    for(int i = 0; i < sigma; ++i) maxc = max(maxc, maxdep[w[u] ^ (1 << i)] + dep[u] - 2 * cdep);
}
inline void renew(int u){maxdep[w[u]] = max(maxdep[w[u]], dep[u]);}
inline void clear(int u){maxdep[w[u]] = -INF;}
template<void(*f)(int)>
void dfs2(int u)
{
    f(u);
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v)
        dfs2<f>(v);
}
int ans[maxn];
void dfs(int u = 1, bool k = false)
{
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != hson[u])
        dfs(v, false);
    if(hson[u]) dfs(hson[u], true);
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) ans[u] = max(ans[u], ans[v]);
    cdep = dep[u];
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != hson[u])
        dfs2<update>(v), dfs2<renew>(v);
    update(u), renew(u);
    ans[u] = max(ans[u], maxc);
    if(!k) dfs2<clear>(u), maxc = -INF;
}
int main()
{
    for(int i = 0; i < (1 << sigma); ++i) maxdep[i] = -INF;
    int n; scanf("%d", &n);
    char s[2];
    for(int i = 2, fa; i <= n; ++i) scanf("%d%s", &fa, &s), add_edge(fa, i, 1 << (s[0] - 'a'));
    getsize();
    dfs();
    for(int i = 1; i <= n; ++i) printf("%d ", ans[i]);
    return 0;
}

长链剖分

其实说来用处也挺少。一个是 $ O(n) $ 收集以深度为下标的信息。另外一个是经过一些处理后 $ O(1) $ 查 $k $ 级祖先。

Ex.

考虑如何统计每个子树中可合并的以深度为下标的信息。(E.g. 点数、点权和、最值, etc)

Sol.

由上节易得一个总 $ O(n \lg n) $ 的重链剖分启发式合并的做法。

这个时候已经用完了重链剖分的几乎所有性质,基于此的复杂度不能更优。但我们注意到这个问题有一个特点:以深度作为关键字而非某种给出属性。其实我们每一步遍历整棵子树是非常浪费的,只需遍历当棵子树统计出来的信息就好,代价是这棵子树的深度。基于此优化复杂度没有变化,因为我们是以子树大小作为重链关键字。设想一棵扫把树,后代不多但是深度深,这是制约我们利用性质的瓶颈。

这启发我们,以深度作为关键字进行树链剖分,也即所谓长链剖分

这个时候上文的复杂度分析失效,因为我们不再能保证链数的量级。

考虑每个子树(以每个点为根的子树)贡献的代价。代价是它的深度即以它为顶端的长链长度。而所有长链不交,量级为 $ O(n) $, 当点我们继承重孩子的数组,代价 $ O(1) $ . 于是我们可以用总 $ O(n) $ 的时间收集每棵子树可合并的以深度为下标的信息。

Ext.

一个自然的想法是,我们是否可以对给出属性进行树链剖分,从而降低带启发式合并的总的复杂度?

以上节为例,若以颜色种量进行剖分。后面的分析仿照上例同理成立。看起来乐滋滋。

但问题是,怎么剖?

k-th ancestor query 1

查询一个点的 $ k $ 级祖先。

Sol.

树上倍增是一个自然的想法,预处理 $ O(n \lg n) $,查询 $ O(\lg n) $ .

使用重链剖分的技术,预处理 $ O(n) $, 查询 $ O(\lg n) $.

分块的话,每个点记录前 $ \sqrt{n} $ 个祖先,预处理 $ O(n\sqrt{n}) $ ,查询 $ O(\sqrt{n}) $ .

树上倍增的倍增表十分强大,但是查询时需要遍历每一个二进制位。

重链剖分可以很方便查找某个祖先,复杂度只跟经过的链数有关。

我们考虑联立树上倍增和树链剖分。注意到长链剖分的性质:

引理 一个点的 $ k $ 级祖先所在长链的长度大于等于 $k $.

Proof. 若祖先与当点在同一条长链上,显然成立;否则祖先所在长链长度必不会小于当前点与祖先连线长度即 $ k $。

我们考虑将当前点向上跳 $ k $ 的二进制最高位长度,即 $ \lfloor k/2\rfloor $ ,则祖先要么在当前长链上,要么在长链向上距离 $\lfloor k / 2 \rfloor $ 以内。

这启发我们在每一条长链的顶端维护两个数组,分别记录这条长链的所有点,和这条长链向上这条链的长度这么长的祖先们。

再预处理出每个可能数的 high-bit,即二进制最高位即可。

复杂度于是做到了 $ O(n \lg n) - O(1) $.

Ex.

给一棵有根树,边上有权值 $ a, b $ ,求一条长度为 $ m $ 的路径,最小化 $ \sum a_i \over \sum b_i $.

Sol.

按 0/1 分数规划的套路,设 $ p:={\sum a_i \over \sum b_i} $,则转换为判定 $ \sum c_i := \sum a_i-pb_i \le 0 $ 是否可行.

二分该 $ p $,对边权确定为 $ c $ 的树,我们考虑用数组 $ f_{u,d} := $ 以 $ u $ 为根向下深度为 $d $ 的 $ \sum c_i $ 的最小值。

转移显然。用上长链剖分启发式合并的技术可以做到单次 $ O(n) $ 得解,总的复杂度 $ O(n \lg n) $.

点分也是类似思路,但需要多一个 $ O(\lg n) $.

Ex.

给一棵有根树,边上有权值 $ a $,求一条长度为 $ [L,R] $ 的路径,最小化 $ \sum a_i $.

Sol.

这样对长度的统计就不能暴力了。

用上数据结构维护 $ f $ 数组咯。复杂度多一个 $ O(\lg n) $,总的是 $ O(n \lg^2 n) $.

听说点分治复杂度超高 der。

其他

平衡树启发式合并

树上分块

dfs序莫队

dfs序主席树


Reference

[1] https://www.cnblogs.com/zzqsblog/articles/6700133.html

[2] http://www.cnblogs.com/zzqsblog/p/6146916.html

[3] http://blog.csdn.net/QAQ__QAQ/article/details/53455462

[4] http://codeforces.com/blog/entry/44351

[5] 林一诺: 浅谈树上启发式合并算法. GDOI 资料集(新第五集)

[6] https://zhuanlan.zhihu.com/p/25984772

百度:长链剖分

Steiner Tree

Problem

给定一个点集,求权值和最小的一个边集使得这些点联通。可以连接到这些点以外的点。

Solution

这个组合最优化问题是 NP-hard 的。

我们考虑使用状压来指数级别枚举。

令 $ f_{i,S}:= $ 包含点 $ i $ 且连接点集中的状态为 $ S $ 的最小花费,可见有以下转移:

$$ f_{i,S}\leftarrow \begin{cases} f_{i,s}+f_{i,S\setminus s} \\ f_{j,S}+w(i,j) & \text{if }(i,j) \in E \end{cases} $$

第二类情况是反直觉的。但只要注意到定义之中我们的 $ i $ 并不一定包含在 $ S $ 以内,就容易知道只有第一种情况是不完备的。

处理第一种情况只是简单的子集枚举 DP。

考虑处理第二种情况。在固定 $ S $ 的情况下满足三角形不等式,所以可以直接用最短路模型来搞。

BZOJ 2595

$ n \times m $ 的网格图,一些点是景点(设有 $ k $ 个),剩下是空地,每一个空地上有些志愿者。

选取最少的志愿者使得经典联通。$ n,m,k\le 10 $.

Sol.

直接按上述做法搞即可。

Code(116056 kb, 1456 ms)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 15, INF = 0x3f3f3f3f;
int a[maxn][maxn], dp[maxn][maxn][1 << maxn];
queue<pair<int, int> > Q;
bool inq[maxn][maxn];
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
struct T
{
    int x, y, z;
    T(int a = -1, int b = -1, int c = -1){x = a, y = b, z = c;}
} pre[maxn][maxn][1 << maxn];
int n, m;
void go(int S)
{
    while(!Q.empty())
    {
        int ux = Q.front().first, uy = Q.front().second; Q.pop();
        for(int i = 0; i < 4; ++i) 
        {
            int vx = ux + dx[i], vy = uy + dy[i];
            if(vx < 0 || vx >= n || vy < 0 || vy >= m) continue;
            if(dp[vx][vy][S] > dp[ux][uy][S] + a[vx][vy])
            {
                dp[vx][vy][S] = dp[ux][uy][S] + a[vx][vy];
                pre[vx][vy][S] = T(ux, uy, S);
                if(!inq[vx][vy]) Q.push(make_pair(vx, vy)), inq[vx][vy] = true;
            }
        }
        inq[ux][uy] = false;
    }
}
bool vis[maxn][maxn];
void dfs(int i, int j, int s)
{
    vis[i][j] = true;
    T t = pre[i][j][s];
    if(t.x == -1 && t.y == -1) return;
    dfs(t.x, t.y, t.z);
    if(t.x == i && t.y == j) dfs(t.x, t.y, s - t.z);
}
int main()
{
    read(n, m);
    int k = 0;
    memset(dp, INF, sizeof dp);
    for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j)
    {
        read(a[i][j]);
        if(a[i][j] == 0) dp[i][j][1 << k] = 0, ++k;
    }
    int N = 1 << k;
    for(int S = 0; S < N; ++S) 
    {
        if(S == N - 1)
            int a = 0;
        for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) 
        {
            for(int s = S & (S - 1); s; s = (s - 1) & S)
            {
                int k = dp[i][j][s] + dp[i][j][S - s] - a[i][j];
                if(k < dp[i][j][S]) dp[i][j][S] = k, pre[i][j][S] = T(i, j, s);
            }
            if(dp[i][j][S] < INF) Q.push(make_pair(i, j)), inq[i][j] = true;
        }
        go(S);
    }
    int x = -1, y = -1;
    for(int i = 0; i < n && x == -1; ++i) for(int j = 0; j < m && x == -1; ++j) if(a[i][j] == 0) x = i, y = j;
    dfs(x, y, N - 1);
    printf("%d\n", dp[x][y][N - 1]);
    for(int i = 0; i < n; ++i, puts("")) for(int j = 0; j < m; ++j)
        if(a[i][j] == 0) putchar('x');
        else if(vis[i][j]) putchar('o');
        else putchar('_');
    return 0;
}

BZOJ 4774

$ n $ 点 $ m $ 边,选出权值最小的一个边集使得 $ i,n-i+1,\forall1\le i\le d $ 联通。

$ n,m\le10^4,1\le d\le 4 $.

Sol.

把 ST 处理出来。

注意到 ST 可能存在配对的边不相连通的情况(其实应该叫做 Steiner Trees),所以还要在做一次子集 DP.

Code(41180 kb, 5904 ms)

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 10, maxm = 1e4 + 10, INF = 0x3f3f3f3f;
struct E{int v, n, w;}e[maxm << 1];
int h[maxm], ec = 1;
inline void add_edge(int u, int v, int w){e[ec] = (E){v, h[u], w}; h[u] = ec++;}
queue<int> Q; bool inq[maxm];
int f[maxm][1 << maxn], g[1 << maxn];
int main()
{
    int n, m, d, k = 0; read(n, m, d);
    memset(f, INF, sizeof f);
    for(int i = 1; i <= d; ++i) f[i][1 << k] = 0, ++k;
    for(int i = n; i > n - d; --i) f[i][1 << k] = 0, ++k;
    int u, v, w; while(m--) read(u, v, w), add_edge(u, v, w), add_edge(v, u, w);
    int N = 1 << k;
    for(int S = 1; S < N; ++S)
    {
        for(int u = 1; u <= n; ++u) 
        {
            for(int s = S & (S - 1); s; s = (s - 1) & S)
                f[u][S] = min(f[u][S], f[u][s] + f[u][S - s]);
            if(f[u][S] < INF) Q.push(u), inq[u] = true;
        }
        while(!Q.empty())
        {
            int u = Q.front(); Q.pop(); inq[u] = false;
            for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(f[v][S] > f[u][S] + e[i].w)
            {
                f[v][S] = f[u][S] + e[i].w;
                if(!inq[v]) Q.push(v), inq[v] = true;
            }
        }
    }
    memset(g, INF, sizeof g);
    N = 1 << d;
    for(int S = 1; S < N; ++S) for(int u = 1; u <= n; ++u) g[S] = min(g[S], f[u][S | (S << d)]);
    for(int S = 1; S < N; ++S) for(int s = S & (S - 1); s; s = (s - 1) & S) g[S] = min(g[S], g[s] + g[S - s]);
    printf("%d", g[N - 1] == INF ? -1 : g[N - 1]);
    return 0;
}

BZOJ 4006

给定一个图,有一些频道,包含一些点,要求频道内的点联通。求最小代价。

$ n \le 1000, m\le 3000, p \le 10 $.

Sol.

求 STs. 然后再对每一个频道枚举一次子集合并。

Code(129828kb, 22016ms)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1000 + 5, maxm = 3000 + 5, maxp = 10 + 5, INF = 0x3f3f3f3f;
struct E{int v, n, w;}e[maxm << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v, int w){e[ec] = (E){v, h[u], w}; h[u] = ec++;}
queue<int> Q; bool inq[maxn];
map<int, int> mm;
int mc = 1;
int ma[1 << maxp], f[maxn][1 << maxp], g[1 << maxp];
int main()
{
    int n, m, p; read(n, m, p);
    int u, v, w; while(m--) read(u, v, w), add_edge(u, v, w), add_edge(v, u, w);
    memset(f, INF, sizeof f); //memset(ma, INF, sizeof ma);
    int c, d, k = 0; while(p--) read(c, d), (!mm[c] ? mm[c] = mc++ : true), f[d][1 << k] = 0, ma[1 << mm[c] - 1] |= 1 << k, k++;
    int N = 1 << k;
    for(int S = 1; S < N; ++S)
    {
        for(int u = 1; u <= n; ++u)
        {
            for(int s = S & (S - 1); s; s = (s - 1) & S) f[u][S] = min(f[u][S], f[u][s] + f[u][S - s]);
            if(f[u][S] < INF) Q.push(u);
        }
        while(!Q.empty())
        {
            int u = Q.front(); Q.pop(); inq[u] = false;
            for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(f[v][S] > f[u][S] + e[i].w)
            {
                f[v][S] = f[u][S] + e[i].w;
                if(!inq[v]) Q.push(v), inq[v] = true;
            }
        }
    }
    memset(g, INF, sizeof g);
    N = 1 << mc - 1;
    for(int S = 1; S < N; ++S) 
        ma[S] = ma[S - (S & -S)] | ma[S & -S];
    for(int S = 1; S < N; ++S) for(int i = 1; i <= n; ++i) 
        g[S] = min(g[S], f[i][ma[S]]);
    for(int S = 1; S < N; ++S) for(int s = S & (S - 1); s; s = (s - 1) & S)
        g[S] = min(g[S], g[s] + g[S - s]);
    printf("%d\n", g[N - 1]);
    return 0;
}

Network Flow(I) - Basic Max-Flow Algorithms

网络流系列笔记:基础最大流算法。

谁能想到一天前我还半会不会 Dinic 呢。

网络流中最基础的部分应该就是求最大流了吧。

按理说如果是讲义的话应该从基础概念入手。

我也有这么考虑过严格化搭建模型框架,但太麻烦了。

而且这只是我的专题复习笔记。默认的前置知识以我的储备为准咯。

增广路定理证明。

Ex: LOJ #101

以下可以视为解决本道例题。代码最后给出。

两大类算法:基于增广路和基于预流推进。

Edmonds-Karp: $ O(nm^2) $

不好意思忘了是什么了。

Dinic: $ O(n^2m) $

将原图分层。然后开始 DFS 寻找增广路,每次只走相邻层的边。由增广路定理得解为正确。

然后可见分层起到优化复杂度的效果。

Complexity

首先可知,DFS 退出的时候,可以增广的所有增广路都已完成。考虑每一次 $ t $ 的标号,若和上次一样,则意味着上次并未增广完。而且必不可能标号更小。从而 $ t $ 的标号严格递增,这样 $ O(n) $ 次阶段一定可以求完最大流。

然后看 DFS 的复杂度。好像可以发现就是 $ O(nm) $ 的,我还不知道怎么严格证。

总的就是 $ O(n^2m) $ 了。

优化

我们来考虑一些常数优化,不 wys 的那种。

  1. 当前流量为 $ 0 $ 的时候直接返回。
  2. 增广过程中,如果一个点的标号没有被修改过,那么遍历它的出边的时候无需从头遍历,从最后访问的边开始就可,因为可能这条边还有残余。

注意

按理来说,我使用前向星每次都需要把链表头 memcpy 一次给记录访问边的 cur 数组。

然后在 LOJ 那种有毒的范围会被卡到 TLE.

使用 vector 记录边下标反而能过。

这启发我们 memcpy 实际上是非常慢的,不比 memset . 所以这使我们使用 Dinic 的时候会有些顾虑。

ISAP(aka. Improved Shortest Augment Path): $ O(n^2m) $

我们发现 Dinic 每次重新计算标号特别傻。走了一遍增广路之后标号的变化是肯定跟增广路相关,且是某种意义上连续的,这启发我们使用这个性质。

我们考虑 DFS 过程中修改标号。

具体来说,用 $ d_i $ 表示编号为 $ i $ 的点到终点的距离,和 Dinic 类似,我们只沿 $ (u, v) : d_u = d_v+1 $ 这样的边增广。如果增广不了了那么这个点的标号就过时了,需要改为出边编号最小的加一。这样增广下去,当起点到终点距离超过 $ n $ 的时候意味着不存在增广路了,算法退出。

Complexity

复杂度上界与 Dinic 的分析相同。

优化

  1. 从终点反向 BFS 求出初始标号。 $ O(n+m) $.
  2. (GAP)如果出现断层,则必不存在增广路,此时算法退出,维护一个 gap 数组记录某深度的点个数,深度发生变化时检查是否变为 $0$ 即可。
  3. 每次更新标号不必重新求最短路。注意到最短路修改具有连续性,只需给标号加一。
  4. 同 Dinic.

备注

在朴素 Dinic、魔改 Dinic 和 HLPP 中对本题跑得最稳定和最快。

实践中也挺快的,写起来也挺短。

可能成为主力用途。

HLPP(aka. Highest Label Preflow Push): $ O(n^2\sqrt{m}) $

考虑怎么手算网络流。从源流到汇,遇到不够就减。这是预流推进

思想

每个结点视为维护一个水池。源水深无限。维护队列,把源推进去。取出一个点,沿边把水按流量推到相邻点,该点加入队列。

这即是主要思想。一个显而易见的弊端是,两个点来回推,进入死循环。

我们仿照分层图的标号,引入高度的概念。源高度为 $n $, 汇为 $ 0 $ ,其他初始为 $ 0 $ ,而且我们规定,水只往下一层流。即只推边 $ (u,v):d_u=d_v+1 $.

如果一个点有水,但是周围点都比他高,我们抬高这个点,因为高度连续,每次这样高度加一,一直到 $ n + 1 $ 流回源。

Complexity

将队列改为优先队列,每次取最高标号的点,即为高标推进。

(Tarjan & Goldberg, 1986) 证明了复杂度为 $ O(n^2\sqrt{m}) $.

优化

  1. (GAP)抬高 $ 1 $ 的时候,如果这个高度没有其他点,则直接将高度大于其的全部置为 $ n + 1 $ 回流到源,因为此时必不存在增广路。

备注

实践中跑得比 ISAP 慢。原因可能这个界很紧而 ISAP 的界很松。

Code

魔改 Dinic (14081, 151596)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxm = 4e6 + 10, maxn = 1e6 + 10, INF = 0x3f3f3f3f;
struct E{int v, f, c;} e[maxm << 1];
int ec = 2;
vector<int> G[maxn];
inline void add_edge(int u, int v, int w)
{
    e[ec] = (E){v,  0, w}; G[u].push_back(ec++); 
    e[ec] = (E){u, 0, 0}; G[v].push_back(ec++);
}
int d[maxn];
int Q[maxn];
int s, t, n;
bool bfs()
{
    memset(d, INF, sizeof d);
    int head = 0, tail = 0; Q[tail++] = s; d[s] = 0;
    while(head != tail)
    {
        int u = Q[head++]; head %= maxn;
        for(int i = 0; i < G[u].size(); i++) 
        {
            E &ed = e[G[u][i]];
            if(ed.f < ed.c && d[ed.v] == INF)
            d[ed.v] = d[u] + 1, Q[tail++] = ed.v, tail %= maxn;
        }
    }
    return d[t] != INF;
}
int cur[maxn];
int dfs(int u, int a = INF)
{
    if(!a || u == t) return a;
    int flow = 0, f;
    for(int &i = cur[u]; i < G[u].size(); i++)
    {
        E &ed = e[G[u][i]];
        if(d[ed.v] == d[u] + 1 && (f = dfs(ed.v, min(a, ed.c - ed.f))) != 0)
        {
            ed.f += f, e[G[u][i] ^ 1].f -= f, flow += f, a -= f;
            if(!a) return flow;
        }
    }
    return flow;
}
long long ret;
long long dinic()
{
    ret = 0;
    while(bfs()){memset(cur, 0, sizeof cur); ret += dfs(s);}
    return ret;
}
int m, u, v, w;
int main()
{
    read(n, m), read(s, t);
    while(m--) read(u, v, w), add_edge(u, v, w);
    printf("%lld\n", dinic());
    return 0;
}

ISAP(10358, 192120)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e6 + 5, maxm = 5e6 + 5, INF = 0x3f3f3f3f;
struct E{int v, n; long long f, c; }e[maxm << 1];
int h[maxn], ec = 2;
inline void add_edge(int u, int v, long long w) {e[ec] = (E){v, h[u], 0, w}, h[u] = ec++, e[ec] = (E){u, h[v], 0, 0}, h[v] = ec++;}
int n, s, t;
queue<int> Q;
int d[maxn], gap[maxn], cur[maxn];
long long go(int u = s, long long a = INF)
{
    if(u == t || !a) return a;
    long long flow = 0;
    for(int &i = cur[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(d[u] == d[v] + 1)
    {
        int tmp = go(v, min(a, e[i].c - e[i].f));
        e[i].f += tmp, e[i ^ 1].f -= tmp, flow += tmp, a -= tmp;
        if(!a) return flow;
    }
    if(!(--gap[d[u]])) d[s] = n + 1;
    ++gap[++d[u]], cur[u] = h[u];
    return flow;
}
long long maxflow()
{
    ++gap[d[t] = 1];
    memcpy(cur, h, sizeof h);
    Q.push(t);
    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(!d[v])
            ++gap[d[v] = d[u] + 1], Q.push(v);
    }
    long long ret = go();
    while(d[s] <= n) ret += go();
    return ret;
}
int main()
{
    int m; read(n, m), read(s, t);
    int u, v, w; while(m--) read(u, v, w), add_edge(u, v, w);
    printf("%lld\n", maxflow());
    return 0;
}

HLPP(TLE)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e6 + 5, maxm = 4e6 + 5, INF = 0x3f3f3f3f;
struct E{int v, n, f, c; } e[maxm << 1];
int h[maxn], ec = 2;
inline void add_edge(int u, int v, int w){e[ec] = (E){v, h[u], 0, w}, h[u] = ec++, e[ec] = (E){u, h[v], 0, 0}, h[v] = ec++;}
int n, s, t;
struct P{int x, d; bool operator<(const P& rhs)const{return d < rhs.d;}};
priority_queue<P> Q;
int gap[maxn], d[maxn];
long long w[maxn];
int push(int u, int v, int i)
{
    int f = min(w[u], 1ll * e[i].c - e[i].f);
    e[i].f += f, e[i ^ 1].f -= f, w[u] -= f, w[v] += f;
    return f;
}
void Gap(int dd){for(int i = 1; i <= n; ++i) if(i != s && i != t && d[i] > dd && d[i] <= n) d[i] = n + 1;}
long long maxflow()
{
    d[s] = n, w[s] = INF; Q.push((P){s, d[s]});
    while(!Q.empty())
    {
        int u = Q.top().x; Q.pop();
        if(!w[u]) continue;
        for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if((u == s || d[u] == d[v] + 1) && push(u, v, i) && v != t && v != s)
            Q.push((P){v, d[v]});
        if(u != s && u != t && w[u])
        {
            if(!(--gap[d[u]])) Gap(d[u]);
            ++gap[++d[u]];
            Q.push((P){u, d[u]});
        }
    }
    return w[t];
}
int main()
{
    int m; read(n, m), read(s, t);
    int u, v, w; while(m--) read(u, v, w), add_edge(u, v, w);
    printf("%lld\n", maxflow());
    return 0;
}

Network Flow(II) - Some Extensions

无源汇有上下界可行流 (I)

我们已经会处理只带上界了的。考虑把下界转换掉。

我们建立超级源 $S$ 和超级汇 $T$ ,每条边权值变为 $ w_i:=high_i-low_i $. $ S $ 向每条边终点连流量为 $ low_i $ 的边, 每条边起点向 $ T $ 连流量为 $ low_i $ 的边。

此时 $ S $ 到 $ T $ 跑一边最大流,若 $ S $ 出边均满,则存在可行流。

我们视 $ T $ 与 $ S $ 间存在一条流量为 $ +\infty $ 的边,从而我们注意到每条边被拆成了两个部分:必要边即下界,通过超级源汇连接起来;附加边即上下界差,仍在原图位置上。

显而易见如此构造找到了可行流的充要条件:$ S,T $ 间需满流。但是这条边并不需要显式体现在算法过程中。

有源汇有上下界可行流

参照上节构造,加入 $ t \xrightarrow{+\infty} s $ 即可.

此时原图变为无源汇的循环流。

有源汇有上下界最大流

在跑完可行流以后,删除 $ S, T $ ,跑一次 $ s $ 到 $ t $ 的最大流。

答案显然就是第一次可行流 + 第二次最大流。

有源汇有上下界最小流

在跑完可行流以后,删除 $ S, T $ ,跑一次 $ t $ 到 $ s $ 的最大流。

答案并不显然就是第一次可行流 - 第二次最大流。

其实第二次的效果相等于把没必要的流全部退回去。

无源汇有上下界可行流 (II)

说网络流这种玄学算法……一定要注意常数……

优化连边什么的,让我们来看一下……

然后看到最开始的那个连边思路很tm的sb。一个点往超级源汇可能连了好多好多条边。

那就先提前统计,每个点 $ d_i=\sum low_j $ , 边 $ j $ 连到 $ i $ 贡献正,连出贡献负。

然后 $ d_i > 0 $ 则 $ S \xrightarrow{d_i}i $ , 否则 $ i \xrightarrow{-d_i} T $.

DEL 老年选手智商特别低下。

边数点数傻傻分不清。

源汇和超级源汇傻傻分不清。

边数起始值还能写错也是服气。

LOJ 115 (42, 1780)

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 200 + 10, maxm = 10200 + 10, INF = 0x3f3f3f3f;
struct E{int v, n; long long f, c;} e[maxm << 3];
int h[maxn], ec = 2;
inline void add_edge(int u, int v, long long w){e[ec] = (E){v, h[u], 0, w}; h[u] = ec++; e[ec] = (E){u, h[v], 0, 0}; h[v] = ec++;}
int n;
int d[maxn], cur[maxn], gap[maxn];
long long go(int u = 0, long long a = INF)
{
    if(u == n + 1 || !a) return a;
    long long flow = 0, f;
    for(int &i = cur[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(d[u] == d[v] + 1 && (f = go(v, min(a, e[i].c - e[i].f))))
    {
        e[i].f += f, e[i ^ 1].f -= f, flow += f, a -= f;
        if(!a) return flow;
    }
    if(!(--gap[d[u]])) d[0] = n + 3;
    ++gap[++d[u]]; cur[u] = h[u];
    return flow;
}
queue<int> Q;
long long maxflow()
{
    gap[d[n + 1] = 1] = 1;
    Q.push(n + 1);
    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(!d[v])
            ++gap[d[v] = d[u] + 1], Q.push(v);
    }
    memcpy(cur, h, sizeof h);
    long long ret = go();
    while(d[0] <= n + 2) 
        ret += go();
    return ret;
}
int l[maxm];
int main()
{
    int m; read(n, m);
    long long cnt = 0;
    for(int i = 1, u, v, r; i <= m; ++i) read(u, v), read(l[i], r), cnt += l[i], add_edge(0, v, l[i]), add_edge(u, v, r - l[i]), add_edge(u, n + 1, l[i]);
    if(maxflow() < cnt) puts("NO");
    else
    {
        puts("YES");
        for(int i = 1; i <= m; ++i) printf("%lld\n", l[i] + e[6 * i - 2].f);
    }
    return 0;
}

LOJ 116 (51, 2220)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 202 + 5, maxm = 9999 + 5, INF = 0x3f3f3f3f;
struct E{int v, n; long long f, c; } e[maxm << 3];
int h[maxn], ec = 2;
inline void add_edge(int u, int v, long long w){e[ec] = (E){v, h[u], 0, w}; h[u] = ec++; e[ec] = (E){u, h[v], 0, 0}; h[v] = ec++;}
int n, s, t, S, T;
int d[maxn], gap[maxn], cur[maxn];
long long cnt = 0;
long long go(int u, bool flag = false, long long a = INF)
{
    if(u == t || !a) return a;
    long long flow = 0, f;
    for(int &i = cur[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(d[u] == d[v] + 1 && (f = go(v, flag, min(a, e[i].c - e[i].f))))
    {
        e[i].f += f, e[i ^ 1].f -= f, flow += f, a -= f;
        if(!a) return flow;
    }
    if(!(--gap[d[u]])) d[s] = n + 3;
    ++gap[++d[u]], cur[u] = h[u];
    return flow;
}
void output()
{
    for(int i = 1; i <= n; ++i) for(int j = h[i], v = e[j].v; j; j = e[j].n, v = e[j].v) if(j % 2 == 0)
        printf("%d %d %d %d\n", i, v, e[j].f, e[j].c);
    puts("");
}
queue<int> Q;
long long maxflow(int ss, int tt)
{
    ++gap[d[n + 1] = 1];
    Q.push(n + 1);
    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(!d[v])
            ++gap[d[v] = d[u] + 1], Q.push(v);
    }
    memcpy(cur, h, sizeof h);
    s = 0, t = n + 1;
    long long ret = go(0);
    while(d[0] <= n + 2) ret += go(0);
    if(ret < cnt) return -1;
    // output();
    s = ss, t = tt, S = 0, T = n + 1;
    memset(gap, 0, sizeof gap); memset(d, 0, sizeof d);
    ++gap[d[tt] = 1];
    Q.push(tt);
    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(!d[v] && ((i % 2 == 1 && e[i^1].f < e[i^1].c) || (i % 2 == 0 && e[i].f < e[i].c)))
            ++gap[d[v] = d[u] + 1], Q.push(v);
    }
    memcpy(cur, h, sizeof h);
    ret = go(s, true, INF);
    // output();
    while(d[s] <= n + 2) ret += go(s, true, INF);
    return ret;
}
int main()
{
    int m, s, t; read(n, m); read(s, t);
    int u, v, l, r; while(m--) read(u, v), read(l, r), cnt += l, add_edge(0, v, l), add_edge(u, v, r - l), add_edge(u, n + 1, l);
    add_edge(t, s, INF);
    long long ret = maxflow(s, t);
    if(ret == -1) puts("please go home to sleep");
    else printf("%lld\n", ret);
    return 0;
}

LOJ 117 (1497, 18920)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 50003 + 5, maxm = 125003 + 5;
const long long INF = 0x3f3f3f3f3f3f3f;
struct E{int v, n; long long f, c; } e[maxm << 3];
int h[maxn], ec = 2;
inline void add_edge(int u, int v, long long w){e[ec] = (E){v, h[u], 0, w}; h[u] = ec++; e[ec] = (E){u, h[v], 0, 0}; h[v] = ec++;}
int n, s, t, S, T;
int d[maxn], gap[maxn], cur[maxn];
long long cnt = 0;
long long go(int u, long long a = INF)
{
    if(u == t || !a) return a;
    long long flow = 0, f;
    for(int &i = cur[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(d[u] == d[v] + 1 && (f = go(v, min(a, e[i].c - e[i].f))))
    {
        e[i].f += f, e[i ^ 1].f -= f, flow += f, a -= f;
        if(!a) return flow;
    }
    if(!(--gap[d[u]])) d[s] = n + 3;
    ++gap[++d[u]], cur[u] = h[u];
    return flow;
}
void output()
{
    for(int u = 0; u <= n + 1; ++u)
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v)
        printf("%d %d %d %d\n", u, v, e[i].f, e[i].c);
}
queue<int> Q;
long long maxflow(int ss, int tt)
{
    ++gap[d[n + 1] = 1];
    Q.push(n + 1);
    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(!d[v])
            ++gap[d[v] = d[u] + 1], Q.push(v);
    }
    memcpy(cur, h, sizeof h);
    s = 0, t = n + 1;
    long long ret = 0;
    while(d[0] <= n + 2) ret += go(0);
    if(ret < cnt) return -1;
    long long t1 = -e[ec - 1].f; ret = 0;

    //output();
    s = tt, t = ss, S = 0, T = n + 1;
    h[s] = e[h[s]].n;
    h[t] = e[h[t]].n; ec -= 2;
    memset(gap, 0, sizeof gap); memset(d, 0, sizeof d);
    ++gap[d[t] = 1];
    Q.push(t);
    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(!d[v] && v != S && v != T && e[i^1].f < e[i^1].c)
            ++gap[d[v] = d[u] + 1], Q.push(v);
    }
    if(!d[s]) return t1 - ret;
    memcpy(cur, h, sizeof h);
    while(d[s] <= n + 1) ret += go(s);
    return t1 - ret;
}
int main()
{
    int m, s, t; read(n, m); read(s, t);
    int u, v; long long l, r; while(m--) read(u, v), read(l, r), cnt += l, add_edge(0, v, l), add_edge(u, v, r - l), add_edge(u, n + 1, l);
    add_edge(t, s, INF);
    long long ret = maxflow(s, t);
    if(ret == -1) puts("please go home to sleep");
    else printf("%lld\n", ret);
    return 0;
}