灯又烬

题解

学习笔记(4) 未归档(2) 算法总结(2)

/ 注册

全部文章 / 题解（共27篇）

[网络流24题] 运输问题来自专栏

题意题解这题..和分配问题不是同一道题吗...同样的建图方式直接跑最小费用最大流即可。将边权变负再跑一遍取负得最大费用。详细题解见 https://blog.nowcoder.net/n/9a823354bd454d0aa33fcbac1c2fb831 code #include <b...

2020-10-09

1 663

[网络流24题] 负载平衡问题来自专栏

题意题解最小费用流。对于每一个点，考虑达到平衡所需操作，是否需要运出或运入货物。建图：设源点s和汇点t.对于所有需要运出货物的点i，令s与i连边，流量为需要运出的货物数量，费用为0。对于所有需要运入货物的点j，令j与t连边，流量为需要运入的货物数量，费用为0。对于相邻两节点，建双向边，流量无...

2020-10-08

1 900

[网络流24题] 分配问题来自专栏

题意题解最大最小费用流直接求解。建图：设源点s，汇点t。对每个源点s与人i连边，边流量为1，费用为0，用来控制每个人只能做一个工作。对于每个工作j与汇点t连边，边流量为1，费用为0，用来控制每个工作只能做一次。对每个人i，工作j建边，边流量为1，费用为效益即权值。直接跑最小费用流即可求得...

2020-10-08

1 640

[网络流24题] 太空飞行计划问题（最大权闭合子图模型）来自专栏

题意该模型为最大权闭合子图模型（看了题解才知道）。即，给定若干个点，每个点有正权值和负权值，选择一个权值则必须选择其后继点，求权值最大子图。模型解法即证明学习自 https://blog.csdn.net/can919/article/details/77603353 题解考虑建图：源点与所...

2020-10-08

1 845

[网络流24题] 最小路径覆盖问题来自专栏

题意求图G的最小路径覆盖并输出路径题解一个忘记了很久的定理,回去翻了翻白书|最大匹配| + |最小边覆盖| = |V||最大独立集| + |最小顶点覆盖| = |V||最大匹配| = |最小顶点覆盖| 求解最小边覆盖，只需要构造二分图找到最大匹配也就是最大流再用顶点总数减去即可。对于路径输出...

2020-10-08

1 757

[网络流24题] 飞行员配对方案问题来自专栏

题意题解二分图匹配裸题不过既然是在网络流24题里面..还是不用匈牙利解了吧建图设超级源点s，超级汇点t对于每个外籍飞行员i，连一条s-i流量为1的边对于每个英国飞行员j，连一条j-t流量为1的边对与每个给定的配对方案，连一条i-j流量为1的边直接跑dinic即可，得到最大流就是能派出的飞机...

2020-10-08

1 765

Codeforces Round #675 (Div. 2) C 来自专栏

这场真的够了...开局看d只有1500分就去开d了..40多分钟没开出来直接自闭放弃比赛，这会一看变成2300分了。。欺骗感情不然这场完全可以手速上分的。题意给出一个长度为< 1e5 的正整数n求解这个数删掉一个任意字串后留得的整数之和求模1e9+7; 题解对每位分别计算贡献。对第i位...

2020-10-06

1 719

Educational Codeforces Round 69 D [dp] 来自专栏

题意给出长度为n的序列a，与两个整数m,k,选择一个子数组，令最大。题解设dp数组代表前i个数字中，选择第个数字作为子数组中第的数字时的最大值。很容易得到转移方程当时其他情况 code #include <bits/stdc++.h> #define reg register...

2020-10-04

0 638

Codeforces Round #560 (Div. 3)A-E 来自专栏

先更个这两天练手速的一场吧。 A. Remainder 题意给出一个长度为n的二进制串，若要令该串对1<<x求模后为1<<y，最少需要改动多少位题解水题， 0 ~ y-1位为0，y位为1，y+1 ~ x-1位为0，比较不同即可 Code #include <bit...

2020-10-04

1 907

网络优化 [贪心]

题意游戏***有n名用户，编号从1到n，服务器共有m条服务线，每个用户最多只能登陆一条线，第i条线最多可以容纳v[i]名用户同时在线，且只能给编号在[l[i],r[i]]范围内的用户提供服务。现在希望找出一种合理的资源分配方案，使得同时在线人数最大化，请输出这个最大人数。题解看了一眼数据范围 ...

2020-09-30

6 798