网络流题目乱做

最大流

  • 直接网络流可以确定物品的分配的方案:"[POI2010] MOS-Bridges"[1]
  • 环的限制可以转化为二分图匹配:"Luogu6061 [加油武汉]疫情调查"[2]
  • 每条流量可以表示为一种不交的方案:"Luogu3358 最长 k 可重区间集问题"[3]
  • 扩域可以很好地解决冲突:"Luogu3358 最长 k 可重区间集问题"[3:1]

最大权闭合子图

  • 注意观察,矩阵可以转化为图论的选 or 不选的问题:"[TJOI2015] 线性代数"[4]
  • 最大权闭合子图中,贡献为负数,就默认不计算,选择就会扣除贡献,如果为正数,就默认计算,不选就会扣除贡献:"[NOI2009] 植物大战僵尸"[5]

  

最小割

普通最小割

  • 可以尝试建出最小割图,然后可以考虑分析最小割数量关系:"CF103E Buying Sets"[6]
  • 最小割数量比较小的时候,就是两个点之间的关系比如联通/点双联通/点三联通了:"[CERC2015] Juice Junctions"[7]

最小割树

上下界网络流

  

对偶图最短路

  

Hall 定理

  • 线段树维护 Hall 定理的式子:"[POI2009] LYZ-Ice Skates"[10]
  • 集合具有完备匹配这一性质支持加法:"[CERC2016] 二分毯 Bipartite Blanket"[11]

  

网络流 + 数据结构

  • CDQ 同时对于跨过中点的点对连边:"[SNOI2019] 通信"[12]

  


  1. [POI2010] MOS-Bridges

    有 $n(n \leq 1000) $ 个点和 \(m(m \leq 20000)\) 条边,每条边有两个权值,分别表示从 \(u\)\(v\) 和从 \(v\)\(u\) 的边权。

    求图中的一个欧拉回路,使得回路中的最大边权最小,并输出方案。


    考虑二分答案,转化为判定性问题。

    我们先连最小代价方向的边 \((x, y)\),如果另外方向的边可以用,那么就可以让 \(deg_x \gets deg_x - 2, deg_y \gets deg_y + 2\),因此我们可以把度数按照大小分类,接着跑网络流即可。(前提是所有节点 \(deg_x \mod 2 = 0\)

    有几个细节:

    • 最后输出方案的时候不能混合型的欧拉回路,应该根据网络流流量情况建边跑有向图欧拉回路。
    • 二分之前一定要判断这个图是否是弱联通的

    ↩︎

  2. Luogu6061 [加油武汉]疫情调查

    给一个有向图,求用若干个环(或点)将整张图覆盖的最小花费,环的代价就是环长,点的代价就是点的权值。

    \(n \le 500, m \le 5000\)


    想到基环树,我们会想到什么呢?就是环!如果基环树上的每个点的出边只有一条,且互不相同,那么就是若干个环以及自环了,这个就是匹配!

    考虑一张二分图,每个左部点和右部点的边权为其距离(如果编号相同,则为点权),那么题目的限制就是求一个完美匹配

    为什么呢?因为把匹配边连起来,一定形成环和若干个单点。

    于是比较暴力的想法:直接建图,然后 KM 或者费用流,复杂度 \(\mathcal O(n^4)\) ,因为新的 \(m\) 已经到了 \(n^2\) 级别。

    大概率会被卡,考虑更加简单的做法:

    拆点,连边 \((S,x, 1, 0), (x, x', 1, a_i), (x', T, 1, 0), (u, v', \infty, w), (x', x, \infty, 0)\),最后一条边就方便了环的限制的刻画。

    跑费用流即可,复杂度 \(\mathcal O(n^2 m)\)↩︎

  3. Luogu3358 最长 k 可重区间集问题

    给定实直线 \(\text{L}\)\(n\) 个开区间组成的集合 \(\mathbf{I}\),和一个正整数 \(k\),试设计一个算法,从开区间集合 \(\mathbf{I}\) 中选取出开区间集合 \(\mathbf{S}\subseteq\mathbf{I}\),使得在实直线 \(\text{L}\) 上的任意一点 \(x\)\(\text{S}\) 中包含 \(x\) 的开区间个数不超过 \(k\),且 \(\sum_{z\in\text{S}}\lvert z\rvert\) 达到最大(\(\lvert z\rvert\) 表示开区间 \(z\) 的长度)。

    这样的集合 \(\mathbf{S}\) 称为开区间集合 \(\mathbf{I}\) 的最长 \(k\) 可重区间集。\(\sum_{z\in\text{S}}\lvert z\rvert\) 称为最长 \(k\) 可重区间集的长度。

    对于给定的开区间集合 \(\mathbf{I}\) 和正整数 \(k\),计算开区间集合 \(\mathbf{I}\) 的最长 \(k\) 可重区间集的长度。

    \(n \le 300, k \le 3\)


    我们可以按照将方案划分为 \(k\) 个两两不相交的区间组,因此,可以考虑如下建图:

    • \((S, 1, k, 0)\)
    • \((i,i+1, k, 0)\)
    • \((a_i, b_i, 1, b_i - a_i)\)

    然后离散化后最大费用最大流就行了。 ↩︎ ↩︎

  4. [TJOI2015] 线性代数

    为了提高智商,ZJY 开始学习线性代数。

    她的小伙伴菠萝给她出了这样一个问题:给定一个 \(n \times n\) 的矩阵 \(B\) 和一个 \(1 \times n\) 的矩阵 \(C\)。求出一个 \(1×n\) 的 01 矩阵 \(A\),使得 \(D=(A×B-C)×A^{\sf T}\) 最大,其中 \(A^{\sf T}\)\(A\) 的转置,输出 \(D\)

    \(1 \leq n \leq 500\)


    注意到 \(A\) 是一个 \(01\) 矩阵,那么可以代表选或者不选,因此 \(B\) 的意义就是 \(i, j\) 同时选的收益, \(C\) 的意义就是 \(i\) 的代价,接着就是最大权闭合子图了。 ↩︎

  5. [NOI2009] 植物大战僵尸

    给出一个 \(n \times m\) 的网格图,每个点有一个植物,每个植物有其价值 \(P\)(可能为负数),然后有其保护位置(植物不死,僵尸就不能到那里),现在僵尸只能从某一行最后一列开始进攻并且吃掉植物,最大化僵尸最后的收益。

    \(n \le 20, m \le 30\)


    最大权闭合子图板子。

    考虑先 拓扑排序,删掉那些永远不可能吃的位置,如果最后某个植物和 \(S\) 联通,那么就是会被吃,否则与 \(T\) 联通,就不被吃。

    • \(P \ge 0\) : \(ans \gets ans + P\), \((S, x, 0), (x, T, P)\)
    • \(P < 0\) : \((S, x, -P), (x, T, 0)\)

    ↩︎

  6. CF103E Buying Sets

    有一个大小为 \(n \le 300\) 的全集,每个元素是一个数,有 \(n\) 个子集。题目保证任意 \(k\) 个子集的并的大小 \(\geqslant k\)

    每个子集有一个可正可负的权值,你需要选出一些子集使得这些子集并的大小等于子集个数,且所选子集的权值和最小。可以为空集。


    神仙转换.jpg

    有一个比较奇怪的事情,\(n\) 个子集。

    我们考虑源点向每个集合连边,边权为 \(\infty - w\),如果割掉就代表不选,每个集合向数连边 \(\infty\),数向汇点连边 \(\infty\)。跑最大流,假设边权全是正的,因为有完备匹配,那么割边条数一定 \(\ge n\),又边权到了 \(\infty\),那么割边数目 \(\le n\),因此割边数目 \(=n\)

    因此不选的集合 + 选的数字 = \(n\),也就是 并集大小 = 集合个数。最后贡献取反即可。 ↩︎

  7. [CERC2015] Juice Junctions

    给出一张 \(n \le 3000\) 个点,\(m \le 4500\) 条边的无向图,每条边边权为 \(1\),每个点度数不超过 \(3\),求 \(\sum\limits_{a < b} \mathrm{mincut}(a, b)\)


    度数不超过 \(3\),也就说明最小割不超过 3。

    分集中情况进行讨论:

    • 如果两个点不连通,那么答案为 \(0\)
    • 如果两个点联通,但是进行并不属于同一个点双联通分量,那么为 \(1\)
    • 如果两个点是属于同一个点三联通分量,那么为 \(3\),否则为 \(2\)

    现在的问题就是如何判断两个点是否属于同一个点三联通分量了。

    注意到 \(m \le 4500\),于是可以考虑暴力删掉一条边,然后去判断每个点的点三联通分量情况,共 \(m\) 轮,每个点可以存一个 Hash 值,时间复杂度 \(\mathcal O(n^2 + m^2)\)↩︎

  8. 最小割树

    构建方法

    每次 rand 两个点 \(x, y\) ,然后求出这两个点之间的最小割,在最小割树上连边 \((x, y)\),边权为最小割,然后会将整个集合分为两个小集合,递归下去不断构建即可。

    构建复杂度为 \(\mathcal O (n^3m)\)

    性质

    \(a, b\) 的最小割等于 \((a, b)\) 在最小割树上边的最小值。

    下文定义 \(\lambda (a, b)\)\(a, b\) 的最小割。

    性质 1

    对于边 \((x, y)\)\(p, q\) 分别属于该边两侧的子树,则有 \(\lambda(x, y) \ge \lambda(p, q)\)

    如果不成立,那么割 \((x, y)\) 的代价割不掉 \((p, q)\)\(p, x\) 联通, \(q, y\) 联通,于是 \((x, y)\) 没有割掉。

    性质 2

    对于任意不同的 \(a, b, c\)\(\lambda(a, b) \ge \min\{\lambda(b, c), \lambda(a,c)\}\)

    假设最小的是 \(\lambda(a, b)\),假设 \(c\) 在割掉 \((a, b)\) 之后和 \(b\) 联通,那么由性质 1,\(\lambda(a, b) \ge \lambda(a, c)\),有因为假设 \(\lambda(a, b)\) 最小,于是 \(\lambda(a, b) = \lambda(a, c)\)

    于是最小值至少有两个,下面就很好说明了。

    性质 2 推论

    对于 \(a, b\), \(\lambda(a, b) \ge \min\{\lambda(a, a_1),\lambda(a_1, a_2)\dots,\lambda(a_t, b)\}\)


    综合"性质 1"[13] 和 "性质 2 推论"[14],可得

    \(a, b\) 的最小割等于 \((a, b)\) 在最小割树上边的最小值。

    int get(int x, int y) { 
        F :: reset(); F :: setst(x, y); 
        rep(i, 1, m) F :: link(u[i], v[i], w[i]), F :: link(v[i], u[i], w[i]); 
        return F :: runit(); 
    }
    
    void build(int l, int r) {
        if(l == r) return; int x = p[l], y = p[r], w = get(x, y);
        G[x].eb(y, w); G[y].eb(x, w);
        top = 0, top2 = l; rep(i, l, r) if(!F :: d[p[i]]) q[++top] = p[i]; else  p[top2++] = p[i];
        int cur = r; while(top) p[cur--] = q[top--];
        build(l, cur); build(cur + 1, r);
    }
    

    ↩︎

  9. CF343E Pumping Stations

    \(n \le 100\) 个点,\(m \le 1000\) 条边的带权无向图。

    你需要构造一个排列,收益为 \(\sum_{i=2}^n \mathrm{mincut}(a_{i-1},a_i)\)

    \(\mathrm{mincut}(S,T)\) 表示图中 \(S\) 为源点,\(T\) 为汇点的最小割。

    求最大的收益,并输出方案。


    首先建立最小割树,然后定义两点之间距离为其在最小割树上边权的 \(\min\) 值,问题就是:求一个排列,使得其路径之和最长。

    因为是 \(\min\) 值作为路径,因此,答案的上界就是所有边权之和,我们可以考虑构造一种方案使得答案到达上界:

    • 树分治,然后每次在这个树中找到边权最小的边,对于 \((x, y)\) 在树上的路径,如果跨过该边,那么距离就是该边权值了。
    • 因为该权值最小,我们要先尽量不经过这条边,分别把分出的两个集合走完,最后在跨过这条边,刚好经过一次。
    • 因此最后的答案是可以达到所有边权之和这一上界的。

    ↩︎

  10. [POI2009] LYZ-Ice Skates

    滑冰俱乐部初始有 \(1 \dots n\) 号码溜冰鞋各 \(k\) 双,已知 \(x\) 号脚的人可以穿 \(x\dots x + d\) 号码的鞋子。现在有 \(m\) 次操作,每次两个数 \(r,x\),表示 \(r\) 号脚的人来了 \(x\) 个,\(x\) 为负表示离开。对于每次操作,输出溜冰鞋是否足够。

    \(r \le n - d, n,k,m\leq5*10^5, k\leq10^9\)


    由 Hall 定理,记前缀和为 \(s_i\),那么我们就是要:

    \[\min_{l \le r} \{k(r + d - l) - (s_r - s_l)\} \ge 0
    \]

    这个非常好办,拆项然后线段树维护。 ↩︎

  11. [CERC2016]二分毯 Bipartite Blanket

    在二分图中,所有点被划分成了两个不相交的集合 \(A\)\(B\),每条边都恰好连接着某个 \(A\) 和某个 \(B\)。一个匹配是一个边集,满足没有任何两条边有相同的端点。我们称一个匹配 \(M\) 覆盖了点集 \(V\) 当且仅当 \(V\) 中的每个点都是 \(M\) 中至少一条边的端点。

    给定一个二分图,每个点有一个正整数权值。定义一个点集的权值为其中所有点的权值之和。

    给定一个参数 \(t\),请统计有多少点集 \(V\),满足 \(V\) 的权值不小于 \(t\),且 \(V\) 被至少一个匹配 \(M\) 覆盖。

    \(1\leq n,m\leq 20\)\(1\leq v_i,w_i\leq 10^7\)\(1\leq t\leq 4\times 10^8\)

    首先有一个结论:

    • 在二分图中,如果 \(A \cap B = \varnothing\),且各自有匹配覆盖 \(A, B\),那么 \(A \cup B\) 也是有匹配覆盖的。

    考虑将覆盖 \(A, B\) 的匹配拿出来,摆到一起:

    down1.png

    于是会形成若干个环和链,分类讨论环和链的情况就行了,长这样:

    down2.png

    剩下的就是对于左边集合和右边集合分别状压 DP check 一下,然后双指针即可。 ↩︎

  12. [SNOI2019] 通信

    \(n\) 个排成一列的哨站要进行通信。第 \(i\) 个哨站的频段为 \(a_i\)

    每个哨站 \(i\) 需要选择以下二者之一:

    1. 直接连接到控制中心,代价为 \(W\)
    2. 连接到前面的某个哨站 \(j\) (\(j<i\)),代价为 \(|a_i-a_j|\)。每个哨站只能被后面的至多一个哨站连接。

    请你求出最小可能的代价和。

    \(1 \leq n \leq 1000\)\(0 \leq W,a_i \leq 10^9\)


    考虑暴力网络流,我们把 \(x\) 拆为两个点 \(x, x'\),如果 \(x\) 流向 \(T\) 则代表和控制中心连接,如果 \(x\) 连向 \(y'\) 那么就代表是连接 \(y\),然后 \(y'\) 在连向 \(T\),代表把最多向后连的限制让给 \(x\)

    于是这么建图:

    • \((S, x, 1, 0)\)
    • \((x, T, 1, W)\)
    • \((x, y', 1, |a_x - a_y|)\) \((x >y)\)
    • \((x', T, 1, 0)\)

    暴力建边很可能 T 掉,于是考虑优化。

    我们可以用 CDQ + 归并处理。 ↩︎

  13. 性质 1

    对于边 \((x, y)\)\(p, q\) 分别属于该边两侧的子树,则有 \(\lambda(x, y) \ge \lambda(p, q)\)

    如果不成立,那么割 \((x, y)\) 的代价割不掉 \((p, q)\)\(p, x\) 联通, \(q, y\) 联通,于是 \((x, y)\) 没有割掉。 ↩︎ ↩︎

  14. 性质 2 推论

    对于 \(a, b\), \(\lambda(a, b) \ge \min\{\lambda(a, a_1),\lambda(a_1, a_2)\dots,\lambda(a_t, b)\}\)


    综合"性质 1"[13:1] 和 "性质 2 推论"[14:1],可得

    \(a, b\) 的最小割等于 \((a, b)\) 在最小割树上边的最小值。

    int get(int x, int y) { 
        F :: reset(); F :: setst(x, y); 
        rep(i, 1, m) F :: link(u[i], v[i], w[i]), F :: link(v[i], u[i], w[i]); 
        return F :: runit(); 
    }
    
    void build(int l, int r) {
        if(l == r) return; int x = p[l], y = p[r], w = get(x, y);
        G[x].eb(y, w); G[y].eb(x, w);
        top = 0, top2 = l; rep(i, l, r) if(!F :: d[p[i]]) q[++top] = p[i]; else  p[top2++] = p[i];
        int cur = r; while(top) p[cur--] = q[top--];
        build(l, cur); build(cur + 1, r);
    }
    

    ↩︎ ↩︎

本博客作者:Werner_Yin(https://www.cnblogs.com/werner-yin/) ,转载时请注明出处,谢谢支持!

推荐这些技术文章:

动态规划题目选解

时不时可能会更新一两下qwq

Past:自己看完后想了想就自己切掉的题
Present:感觉有点难度或者属于某种没见过的套路的题
Future:思维难度比较高/代码很难写/使用了一些黑科技

难度大致从前往后递增。如果按这种等级算我的 ptt 可能只有 5 点多

CF837D Round Subset Past 4
首先一个数末尾 \(0\) 的个数就相当于其唯一分解中 \(2\) 和 \...

后缀数组题目选讲

后缀数组题目选讲
复习题:luogu题单
CNOI的题
\(1.\)NOI2015 品酒大会
题意:\(\forall i∈[0,n)\)求有多少对后缀满足\(lcp \ge i\)​,以及满足条件的两个后缀的权值乘积的最大值。
我们统计出对于\(1...n\)中的每个\(i\)统计一下有多少个\(lcp=i\)再做个后缀和。
因为\(lcp(i,j)=min_{i<k \le j}{h...

ZJOI 2019 题目选做

正在持续更新咕咕咕咕中。
LOJ3042「ZJOI2019」麻将

今天,可怜想要打麻将,但是她的朋友们都去下自走棋了,因此可怜只能自己一个人打。可怜找了一套特殊的麻将,它有 \(n(n \ge 5)\) 种不同的牌,大小分别为 \(1\) 到 \(n\),每种牌都有 \(4\) 张。
定义面子为三张大小相同或者大小相邻的麻将牌,即大小形如 \(i, i, i(1 \le i \le n)\) ...

BJOI 2018 题目选做

LOJ2492「BJOI2018」二进制

pupil 发现对于一个十进制数,无论怎么将其的数字重新排列,均不影响其是不是 \(3\) 的倍数。他想研究对于二进制,是否也有类似的性质。
于是他生成了一个长为 \(n\) 的二进制串,希望你对于这个二进制串的一个子区间,能求出其有多少位置不同的连续子串,满足在重新排列后(可包含前导 \(0\))是一个 \(3\) 的倍数。两个位置不同的子区间指开始...

线段树合并 & 权值线段树 & 一些题目

https://www.luogu.com.cn/blog/styx-ferryman/xian-duan-shu-ge-bing-zong-ru-men-dao-fang-qi?tdsourcetag=s_pcqq_aiomsg
%%%
权值线段树的一些操作
int getrank(int x){
return query_num(root,1,maxdata,1,x)+1;
}
in...

文章标题:网络流题目乱做
文章链接:https://www.dianjilingqu.com/4076.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>