2023年7月30日发(作者：)
【题解】⽹络流24题2424前⾔题⽬链接：按在洛⾕⾥的难度排序由易到难去刷，⽽不是原来的题号。最⼤流模板：dinic 算法struct Dinic{ struct Edge { int from, to, cap, flow; }; int s, t; //节点数,边数,源点编号,汇点编号 vector
(f = DFS(, min(a, - ))) > 0) { += f; edges[G[u][i] ^ 1].flow -= f; flow += f; flow += f; a -= f; if(a == 0) break; } } return flow; } int maxflow(int _s, int _t) { s = _s; t = _t; int flow = 0; while(BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; }}dinic;最⼩割最⼩割=最⼤流最⼩费⽤最⼤流模板：MCMFstruct MCMF{ struct Edge { int from, to, cap, flow, cost; Edge(int u, int v, int c, int f, int w) : from(u), to(v), cap(c), flow(f), cost(w) {} }; vector
0−>k层，第i层表⽰还剩下多少油2. 节点:1. 源点:
11∗101∗101+12. 汇点:
11∗101∗101+23. 第f层的[r,c]:
f∗101∗101+r∗101+c3. 弧:1. 有加油站:第k层: 向下⼀层正向可达的点连容1费0的边,反向可达的点连容1费B的边.⾮第k层: 向第k层连容1费A的边2. ⽆加油站向下⼀层正向可达的点连容1费0的边,反向可达的点连容1费B的边.⾮第k层: 向第k层连容1费A+C的边3. 源点向第k层[1,1]：容1费04. 每层的[n,n]向汇点：容1费04. 最⼩费⽤最⼤流:最⼤流: 1最⼩费⽤: 答案MCMF mcmf;inline int encode(int f, int r, int c){ return f*101*101 + r*101 + c;}int main(void){ int n=read(), k=read(), A=read(), B=read(), C=read(); int src = 11*101*101+1, dst = 11*101*101+2; e(src, encode(k,1,1), 1, 0); //源边 for(int i=0; i<=k; ++i) //汇边 e(encode(i,n,n), dst, 1, 0); const int go[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; for(int r=1; r<=n; ++r) for(int c=1; c<=n; ++c) { int have = read(); for(int i=0; i for(int dir=0; dir<4; ++dir) { int nr=r+go[dir][0], nc=c+go[dir][1]; if(nr>=1&&nr<=n&&nc>=1&&nc<=n) for(int i=(have?k:1); i<=k; ++i) //⾛格,要求当前位置满油或者没有加油站 e(encode(i,r,c), encode(i-1,nr,nc), 1, dir>>1?B:0); } } cout << (src,dst).second << endl; return 0;}似乎分层之后按最短路也可以做7/24 P3254 圆桌问题m(150)个有若⼲⼈的单位要在n(270)张可以容纳若⼲⼈的餐桌上聚餐，要求同⼀单位的⼈餐桌各不相同。输出⽅案。最⼤流1. 节点:1. 源点: 02. 单位: 1->m3. 餐桌: m+1->m+n4. 汇点: m+n+12. 弧:1. (源点, 单位, 单位⼈数)2. (单位, 餐桌, 1)3. (餐桌, 汇点, 餐桌容量)3. 最⼤流:1. 最⼤流为所有单位总⼈数时, 表⽰成功安排了这些⼈2. 输出⽅案8/24 P2763 试题库问题⼀共有k(20)种试题类型，n道试题(1000)，每道试题都属于若⼲个试题类型。现在要选出m道题且每道题都必须属于给定的⼀种试题类型，输出⽅案。最⼤流1. 节点:1. 源点: 02. 种类: 1->k3. 试题: k+1->k+n4. 汇点: k+n+12. 弧:1. (源点, 种类, 种类所需数量)2. (种类, 对应试题, 1)3. (试题, 汇点, 1)3. 最⼤流:1. 可选试题数, 如果等于⽬标题数则成功组卷2. 输出⽅案9/24 P2764 最⼩路径覆盖问题给定⼀张有向⽆环图，求最⼩路径覆盖，输出⽅案。最⼩路径覆盖是指⼀个最⼩的有向路径集合，且图中的每个节点恰好在其中的⼀条路径上（路径长度可以为0，即只包含1个点）。和魔术球问题有些相似，最坏情况的路径数等于节点数，通过将拆点连弧获得的最⼤流即为最多可以合并⼏条路径。拿节点数⼀减就是答案。拆点最⼤流1. 节点:1. 源点0, 汇点12. 图中第i个点: 左部分i2, 右部分i2+12. 弧:1. (源点,左部分点,1)2. (右部分点,汇点,1)3. (i的左部分,j的右部分,1),前提是原图中i到j有⼀条有向边3. 最⼤流:1. (点数-最⼤流)即为最⼩路径覆盖2. 输出答案输出答案时，可以依次遍历未被访问的所有点，⾸先沿着反向弧找到路径起点，再依次输出并标记访问过即可。10/24 P4014 分配问题有n(100)个⼯作要分配给n个⼈，已知每个⼈做每个⼯作的收益，分别求最⼩和最⼤的时间和。费⽤流1. 节点:1. 源点: 02. ⼈: 1->n3. ⼯件: n+1->2n4. 汇点: 2n+12. 弧:1. (源点, ⼈, 1, 0)2. (⼈, ⼯件, 1, 价值(求最⼤效益则为正,反之则为负))3. (⼯件, 汇点, 1, 0)这道题告诉我们，费⽤是负数时，费⽤流也可以很好的求出结果。11/24 P2762 太空飞⾏计划问题有m个实验和n个仪器，做实验会有收⼊，采购仪器需要花钱，仪器可以重复使⽤。每个实验依赖于若⼲不同的器材，求做哪些实验可以获得最⼤净收益。最⼩割模型：最⼤权闭合⼦图1. 节点:1. 源点: 02. 实验: 1->m3. 仪器: m+1->m+n4. 汇点: m+n+12. 弧:1. (源点, 实验, 实验赞助)2. (实验, 仪器, INF)3. (仪器, 汇点, 仪器花费)3. 最⼩割:1. 最⼤净收益 = 所有实验收益之和-最⼩割2. 输出⽅案对上述⽹络跑最⼩割，显然不会割去中间的INF边，所以此时的S集合即为可⽤的（实验，仪器）组合。注意最⼩割的数值⾥包括了（1.不选择的实验收⼊，2.选择的仪器花费）。此时拿所有实验的总收⼊减去最⼩割的数值，就是（1. 选择的实验收⼊，2.选择的仪器花费的相反数），即为答案。输出⽅案即输出除源点外的S集合，这⾥有⼀个待研究的性质：dinic最后⼀次bfs后，vis为1的节点集合即为最⼩割的S集合。这题输⼊有些烦，列代码如下：Dinic dinic;int main(void){ int m, n; scanf("%d %dn", &m, &n); int src=0, dst=m+n+1, sum=0; for(int exp=1; exp<=m; ++exp) { string line; getline(cin, line); stringstream sin(line); int earn; sin>>earn; sum+=earn; int inses=0, ins; while(sin >> ins) { ++inses; e(exp, ins+m, INF); } e(src, exp, earn); } for(int i=m+1; i<=m+n; ++i) { int cost = read(); e(i, dst, cost); } int ans = w(src, dst); for(int i=1; i<=m; ++i) if([i]) printf("%d ",i ); printf("n"); for(int i=m+1; i<=m+n; ++i) if([i]) printf("%d ",i-m ); printf("n"); cout << ans << endl; return 0;}12/24 P4015 运输问题有m个存有货物的仓库和n个需要货物的商店，给定每个仓库向每个商店运输的单位花费，求最⼩的总运输花费。费⽤流裸题。13/24 P2774 ⽅格取数问题m*n的⽹格中存放着数字，现在要从⽅格中取数，使得数字之和最⼤且任意两个被选中的⽅格没有相邻边。最⼩割模型：⼆分图最⼤权独⽴集弧：（源点，偶数点，点权）（偶数点，相邻奇数点，INF）（奇数点，汇点，点权）答案 = 所有点的点权之和 - 最⼩割。14/24 P2766 最长不下降⼦序列问题给定长为n(500)的数字序列，求1. 最长不下降⼦序列长度s2. 原序列可以抽出多少个长为s的不下降⼦序列3. 当x1和xn可以多次使⽤时，原序列中可以抽出多少个长为s的不下降⼦序列。第⼀问⾸先使⽤O(n^2)或者O(nlogn）⽅法求得LIS长度，并且记录以每个位置为结尾的最长不下降⼦序列长度dp[i]。第⼆问建⽴⽹络图：（源点，dp为1的点，1）（i，i的后继，1），节点j是i的后继当且仅当j>i，save[j]>save[i]，dp[j]=dp[i]+1（dp为s的点，汇点，1）最⼤流即为答案。第三问建⽴⽹络图：（源点，dp为1的点，i==1?INF:1）（i，i的后继，1）（dp为s的点，汇点，i==n?INF:1）最⼤流即为答案。第三问有坑点，需要特判n=1的情况。15/24 P3358 最长k可重区间集问题给定⼀条实直线，n(500)个直线上开端点的线段，⼀个正整数k。求⼀个线段集合，使得集合中的线段在直线上的覆盖次数不超过k，且集合中线段长度之和最⼤。费⽤流经典题：流量控制1. 将直线上的点离散化成1到2n，从头到尾连接起来，容量为k，费⽤为0。2. 每条线段起⽌点连接起来，容量为1，费⽤为线段长度。此时最⼤费⽤即是答案。这道题中⽤主⼲流上的流量来表⽰还可以被覆盖的次数，每次脱离主⼲流时流量减⼀费⽤加上对应权值，汇⼊主⼲流后流量⼜增加。16/24 P4012 深海机器⼈问题给定⼀个P*Q的⽹格，每段⽹格边有对应的价值，现在在⼏个选定位置释放机器⼈，每个位置有固定的释放数量。每个机器⼈只能向东或向南⾛，每段价值只能收集⼀次。有⼏个选定位置可以收集机器⼈，有固定的收集数量。问最终收集的最⼤价值。多源多汇费⽤流有⼀个经典做法可以处理只能收集⼀次的价值：建⽴两组边（a，b，1，value）（a，b，0，INF）17/24 P3355 骑⼠共存问题在n*n的棋盘上有m个障碍，计算棋盘上最多可以放多少个骑⼠（马）使得它们不能互相攻击。（国际象棋不蹩马腿。）可以证明，棋盘上的格⼦及互相攻击的关系构成了⼀张⼆分图。最⼩割模型：⼆分图最⼤独⽴集因为没有涉及到权，只需要对（源点，集合A），（集合A，相连的集合B），（集合B，汇点）都建⽴容量为1的边即可。答案 = 总的可⽤点数 - 最⼩割。18/24 P3357 最长k可重线段集问题给定⼀个平⾯上的n条开线段，⼀个正整数k。求⼀个线段集合，使得集合中线段在x轴上的投影覆盖次数不超过k，且集合中线段长度最⼤。费⽤流：流量控制，分点类似于P3358 最长k可重区间集问题，但是会有垂直于x轴的线段的情况。所以要把直线上每个点分成左部分和右部分，垂直于x轴的线段从⼀个点的左部分连到右部分。其它线段从左端点的右部分连道右端点的左部分。19/24 P1251 餐⼱计划问题餐厅在未来的N天内需要不尽相同的餐⼱数量，餐⼱使⽤⼀次就会脏。1）在需要时可以购买餐⼱，每条花费为p。2）可以把脏餐⼱送去快洗，快洗每条花费为f，需要m天洗好。3）可以把脏餐⼱送去慢洗，慢洗每条花费为s，需要n天洗好。4）脏餐⼱可以暂时不洗。求总的最⼩花费。费⽤流：分点，反向源汇边（？）餐⼱计划问题-费⽤流1. 节点:1. 源点: 02. 汇点: 13. 第i天的早晚: i2, i2+12. 弧:1. (源点, 晚上, 当天脏⽑⼱, 0) //使⽤2. (早上, 汇点, 当天所需⽑⼱, 0) //需求3. (源点, 早上, INF, 购买⽑⼱所花费⽤P) //购买4. (第i天晚上, 第i+m天早上, INF, f) //快洗5. (第i天晚上, 第i+n天早上, INF, s) //慢洗6. (第i天晚上, 第i+1天晚上, INF, 0) //不洗3. 最⼩费⽤最⼤流:最⼩费⽤即为答案这道题分点好想，但是分点之后⽆法进⾏建图。把每⼀天分成早上和晚上，正确的做法是从源点向晚上连边，表⽰获得了脏餐⼱，从早上向汇点连边，表⽰消耗了⼲净餐⼱。⼀个神奇的模型。20/24 P4013 数字梯形问题给定⼀个n⾏，第⼀⾏有m个数字的数字梯形。现在要从顶部m个数字开始找到m条路径，求分别满⾜如下规则时的最⼤m条路径上数字之和。1）m条路径互不相交。2）数字节点处可以相交，边不能相交。3）数字节点和边都可以相交。费⽤流：分点，多模型因为数字上有价值，⾃然考虑分点，上部分与上层节点相连，下部分与下层节点相连，均⽆费⽤，称为外部弧。数字内部上部分与下部分节点相连，称为内部弧，有费⽤（价值）。1. 问题⼀：外部弧与内部弧容量均为1.2. 问题⼆：外部弧容量为1，内部弧容量INF。3. 问题三：内部弧与外部弧容量均为INF。注意，在三个⼦问题中源点向顶层节点上部分的弧容量总是1.在问题1中，底层节点下部分向汇点的弧容量是1，问题2和3中是INF。分别求最⼤费⽤即可。放⼀下⾃认为写的不错的代码：MinCostMaxFlow pro1, pro2, pro3;inline int upp(int i, int j){return (i*64+j)*2;}inline int dow(int i, int j){return (i*64+j)*2+1;}int main(void){ #ifdef _LITTLEFALL_ freopen("","r",stdin); #endif int m=read(), n=read(); int src=0, dst=1; for(int i=1; i<=n; ++i) for(int j=1; j<=m+i-1; ++j) { if(i==1) //源边 { e(src, upp(i,j), 1, 0); e(src, upp(i,j), 1, 0); e(src, upp(i,j), 1, 0); } int v=read(); //拆点边 e(upp(i,j), dow(i,j), 1, -v); e(upp(i,j), dow(i,j), INF, -v); e(upp(i,j), dow(i,j), INF, -v); for(int nj:{j,j+1}) //下层边 { e(dow(i,j), upp(i+1, nj), 1, 0); e(dow(i,j), upp(i+1, nj), 1, 0); e(dow(i,j), upp(i+1, nj), INF, 0); } if(i==n) //汇边 { e(dow(i,j), dst, 1, 0); e(dow(i,j), dst, INF, 0); e(dow(i,j), dst, INF, 0); } } cout << -(src,dst).second << endl; cout << -(src,dst).second << endl; cout << -(src,dst).second << endl; return 0;}21/24 P3356 ⽕星探险问题在n*m的⽹格中，每个⽹格要么是空地，要么是障碍，要么是具有价值的资源。现在在(1,1)放下P个机器⼈，每个机器⼈只能朝南或东移动，机器⼈可以在(n,m)被回收。要求在机器⼈回收数量最多的前提下收集到的资源价值最⼤。输出所有机器⼈的路径。费⽤流：分点，⼀次价值，输出路径因为是节点有价值，所以要分点。因为价值只能收集⼀次，所以建⽴两条边(1,v)和(INF,0)。输出路径可以考虑dfs，每次⾛⼀步就给边上流量减⼀。22/24 P2770 航空路线问题给定⼀张图，找到⼀条从最左侧点到最右侧点再回到最左侧点的经过节点最多的路径。输出答案。费⽤流：分点，输出路径模型类似于[P4013 数字梯形问题]的问题⼀。当最⼤流⼤于等于2时有解，输出路径也可采⽤dfs。注意处理1->n->1的情况。这道题还涉及字符串与数字的转化，码量较⼤。MinCostMaxFlow mcmf;struct Discretization{ vector { if((name)) return dcter[name]; _back(name); return dcter[name] = (); } inline string get(int id) {return save[id-1];}}dct; //将城市名映射为1-n的数字/*费⽤流节点: 源点: 城市1的左部分 汇点: 城市n的右部分 城市i: 左部分i*2, 右部分i*2+1弧: (城市左部分, 城市右部分, 1, -1), 城市为1或n时容量为2 (左边城市右部分, 右边城市左部分, INF, 0)最⼩费⽤最⼤流: 最⼤流>=2, 表⽰有解. 输出路径*/inline int lef(int i){return i*2;}inline int rig(int i){return i*2+1;}int main(void){ #ifdef _LITTLEFALL_ freopen("","r",stdin); #endif int n=read(), v=read(); for(int i=1; i<=n; ++i) { string name; cin>>name; (name); e(lef(i), rig(i), i==1||i==n?2:1, -1); } while(v--) { string city1, city2; cin >> city1 >> city2; int c1 = (city1), c2=(city2); if(c1>c2) swap(c1, c2); e(rig(c1), lef(c2), INF, 0); e(rig(c1), lef(c2), INF, 0); } auto res = (lef(1), rig(n)); if(<2) { printf("No Solution!n" ); return 0; } vector { --[eid].flow; ans[i].push_back(now); now = [eid].to/2; break; } } } ans[0].push_back(n); ans[0].insert(ans[0].end(),ans[1].rbegin(), ans[1].rend()); cout << ((int)ans[0].size()-1) << endl; for(int c : ans[0]) { cout << (c) << endl; } return 0;}23/24 P2754 [CTSC1999]家园有n(13)个空间站，编号为1到n。此外，地球的编号为0，⽉球编号为-1。现在有m(20)个宇宙飞船，每个都有⼀定容量，且在某⼏个空间站或星球之间周期性移动。现在有k（50）个⼈在地球上，需要被送到⽉球上。求最⼩的时间。按时间分层的最⼤流算法（zht算法）整体思路是使⽤并查集判断是否有解，再按时间分层建图，然后枚举时间在残量⽹络中跑最⼤流看什么时候最⼤流⼤于等于⼈数，当前时间就是答案。1. 层: 0到t层，表⽰时间，每层有(n+2)个点数.2. 节点:1. 源点: 02. 汇点: (n+2)∗t+n+1（第t层的⽉球）3. 第f层地球: (n+2)∗f+04. 第f层空间站i: (n+2)∗f+i5. 第f层⽉球: (n+2)∗f+n+1.3. 弧:1. (t层节点, t+1层对应节点, INF)2. (t层节点, t时刻飞船路径到达的节点, 飞船容量)4. 最⼤流:1. 满⾜最⼤流⼤于等于初始⼈数的最⼩时间t即为答案需要注意的是，因为没有单独建源点和汇点，跑出的最⼤流可能会恰⼤于⼈数k，如果以等于⼈数k去判断，会TLE到爆炸（⾎泪教训）。因为是实际意义上的最后⼀篇，放⼀下代码。需要C++111. dinic板⼦可以调⽤的函数⼀共有两个，分别是添加边的addEdge和求最⼤流的maxflow。addEdge会⾃动添加反向弧。struct Dinic{ void addEdge(int from, int to, int cap); int maxflow(int _s, int _t);}dinic;需要两个全局常数 const int M = 100016, INF = 1000000007;2. 飞船get_path可以接收天数，返回某条弧的起始点。struct SpaceShip{ int limit; //⼈数限制 int cycle; //周期 vector (f = DFS(, min(a, - ))) > 0) { += f; edges[G[u][i] ^ 1].flow -= f; flow += f; a -= f; if(a == 0) break; } } return flow; } int maxflow(int _s, int _t) { s = _s; t = _t; int flow = 0; while(BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; }}dinic;/* 按时间分层的最⼤流算法层: 表⽰时间,从0开始,每层有(n+2)的偏移.节点: 源点: 0 汇点: (n+2)*t+n+1 第f层地球: (n+2)*f+0 第f层空间站i: (n+2)*f+i 第f层空间站i: (n+2)*f+i 第f层⽉球: (n+2)*f+n+1.弧: (t层节点, t+1层对应节点, INF) (t层节点, t时刻飞船路径到达的节点, 飞船容量)最⼤流: 满⾜最⼤流等于初始⼈数的最⼩时间t即为答案*/struct SpaceShip{ int limit; int cycle; vector
发布者：admin，转转请注明出处：http://www.yc00.com/xiaochengxu/1690721137a407593.html
评论列表（0条）