单屏网站设计,黑白高端大气网站设计工作室织梦dedecms模板,电商平台搭建构思,上海住房城乡建设网站证件查询前言
不断更新中… 专题的(下)篇将介绍网络流的一些奇奇怪怪的应用和费用流有关的一些套路。
本专题暂时包含三道题#xff1a;
洛谷P1251 餐巾计划问题: 费用流的基本应用 Trade Gym - 100212I: 使用网络流对图论中的边进行调整 codeforces 818G - Four Melodies: 费用…前言
不断更新中… 专题的(下)篇将介绍网络流的一些奇奇怪怪的应用和费用流有关的一些套路。
本专题暂时包含三道题
洛谷P1251 餐巾计划问题: 费用流的基本应用 Trade Gym - 100212I: 使用网络流对图论中的边进行调整 codeforces 818G - Four Melodies: 费用流压缩建图 洛谷P1251餐巾计划问题
题意
见题目链接
题解
这道题我们把选取一张餐巾纸当作是一个单位的流量那么显然来源部不同的餐巾纸他们的费用是不相同的这就引出了费用流(最小费用最大流)的模型。
每一天可以在早上接受r[i]r[i]r[i]数量的餐巾纸同时也可以将r[i]r[i]r[i]数量的餐巾纸送去清洗所以我们需要将每一天拆成两个点分别表示需要餐巾纸的点和送走餐巾纸的点。
需要餐巾纸的点与汇点TTT连边，容量为r[i]" role="presentation" style="position: relative;">r[i]r[i]r[i]费用为000。还要和源点S" role="presentation" style="position: relative;">SSS连边容量为r[i]r[i]r[i]费用为ppp，这代表购买新的餐巾纸的方式。
送走餐巾纸的点需要和两个点进行连边：
送去慢洗，则需要和n" role="presentation" style="position: relative;">nnn天以后的需求点连边容量为infinfinf费用为慢洗一条的费用。
送去快洗则需要和mmm天以后的需求点连边，容量为inf" role="presentation" style="position: relative;">infinfinf费用为快洗一条的费用。注意由于一条餐巾纸洗完了可以存放任意时间所以我们需要在相邻需求点之间连立一条费用为000，容量为inf" role="presentation" style="position: relative;">infinfinf的边代表的含义就是餐巾纸在存放。
如图所示:
优化由于BBB累点之间有边相连，表示餐巾纸可以存放到下一天，那么，我们可以把S#x2212;gt;B" role="presentation" style="position: relative;">S−BS−BS->B的边省略掉只保留S−1BS−1BS->1B这条边表示所有新购买的餐巾纸都在第一天买好然后存放到需要的那一天再使用。
优化图如下
这样建图完成以后跑一个最小费用最大流就可以了。 注意请检查你的板子速度是否可行我的板子速度就太慢了zkw费用流模板了解一下。
参考代码 略 Trade Gym - 100212I
题意
给出A、B两个点集A、B之间有边相连而A和B的内部均无边相连。 题目要求求出最多删除A、B之间的多少边才能使得A中点的度数至少都为2B中点的度数也至少都为2。
题解
先求出每个点的度数从每个点v出发最多能删除deg[v]−2deg[v]−2deg[v]-2条边注意这里是理想情况下不一定能删除这么多。 那么我们就可以建立一个超级源点SSS和超级汇点T" role="presentation" style="position: relative;">TTT从SSS往A" role="presentation" style="position: relative;">AAA点集连边边的容量为deg[v]−2deg[v]−2deg[v]-2从BBB点集往T" role="presentation" style="position: relative;">TTT点连边边的容量为deg[u]−2deg[u]−2deg[u]-2 AAA和B" role="presentation" style="position: relative;">BBB之间的边流量全为111。
从S" role="presentation" style="position: relative;">SSS点流到TTT的每一个为1" role="presentation" style="position: relative;">111的流量都相当于在原图里面删除了这条边。 跑一边最大流就可以得到最多能删除多少边了。在残余网络中做一些小操作就可以把剩余的边输出出来。 网络图如下
总结
网络流可以用于对图论中的边进行调整当图论中的一条边存在流量流过的时候代表该边被“调整”了调整可以具有很多含义比如本题中的“删除”也算“调整”。
参考代码 略 Four Melodies
题意
题目链接
给出nnn个数，输出选四个不相交的melody的所有情况中，4个melody长度总和的最大值。要形成Melody，要求相邻的数字要么相差1" role="presentation" style="position: relative;">111要么相差777的倍数。题解一种很直观的建图方法就是把每个数字拆成2个点in" role="presentation" style="position: relative;">ininin和outoutout然后源点也拆成2个点sss和s#x2032;" role="presentation" style="position: relative;">s′s′s'并把s′s′s'作为费用流的源点。
从s′−ss′−ss'->s建立一条容量为444费用为0" role="presentation" style="position: relative;">000的边。然后从sss点向每个in" role="presentation" style="position: relative;">ininin建立一条容量为111，费用为0" role="presentation" style="position: relative;">000的边。
再从ininin向outoutout建立一条容量为111，费用为#x2212;1" role="presentation" style="position: relative;">−1−1-1的边。从outoutout向汇点ttt建立一条容量为1" role="presentation" style="position: relative;">111费用为000的边。然后对于任意两个node.i,j" role="presentation" style="position: relative;">node.i,jnode.i,jnode. i,j如果iii到j" role="presentation" style="position: relative;">jjj符合相邻的222个条件，那么就从i的out" role="presentation" style="position: relative;">outoutout点向j的ininin点连接一条容量为111费用为0" role="presentation" style="position: relative;">000的边表示他们可以串起来。
这样的话建图的复杂度为O(n2)O(n2)O(n^2)边的个数也为O(n2)O(n2)O(n^2)复杂度太高了因此需要压缩建图。 奇技淫巧当你找不到任何优化的点的时候可以考虑搞一个出错率极小的做法有一个想法就是每个点仅向后面50个点连边。 怎么压缩建图呢
把每个点都扩充成3个点in,mid,outin,mid,outin,mid,out其中ininin往midmidmid 连边容量为111，费用为#x2212;1" role="presentation" style="position: relative;">−1−1-1midmidmid往outoutout连边容量为111，费用为0" role="presentation" style="position: relative;">000。
从ininin往outoutout连边容量为infinfinf费用为000，表示途径这个点。关键的一步来了：
从i这个点往后找第一个使得val[i]=val[j]+1" role="presentation" style="position: relative;">val[i]=val[j]+1val[i]=val[j]+1val[i] = val[j]+1的点jjj，从i.out" role="presentation" style="position: relative;">i.outi.outi.out向j.inj.inj.in连接一条容量为111，费用为0" role="presentation" style="position: relative;">000的边。 从iii这个点往后找第一个使得val[i]=val[j]#x2212;1" role="presentation" style="position: relative;">val[i]=val[j]−1val[i]=val[j]−1val[i] = val[j]-1的点jjj，从i.out" role="presentation" style="position: relative;">i.outi.outi.out向j.inj.inj.in连接一条容量为111，费用为0" role="presentation" style="position: relative;">000的边。 从i这个点往后找第一个使得val[i]−val[j]%70val[i]−val[j]%70（val[i] - val[j]）\%7 == 0 的点jjj，从i.out" role="presentation" style="position: relative;">i.outi.outi.out向j.inj.inj.in连接一条容量为111，费用为0" role="presentation" style="position: relative;">000的边。 这样的话图就算压缩完成了不需要两两比较建图。 图举例
