题目链接 最小割模板题 根据最小割最大流定理 \(f(s,t)_{max}=c(s,t)_{min}\) 证明如下: \(f(s,t)\leq c(s,t)\) \(f(s,t)=S\text{出边流量}-S\text{入边流量}\leq S\text{出边流量}=c(s,t)\) 当\(s,t\)不联通时，入边流量为 0 流，而出边流量满流。 所以最小割等于最大流 而割边数只需要把所有边权调

最大流模板题 dinic 是在残量网络上分层后\(\mathjaxcal{O}(n^2m)\)找增广路的算法 ## 定义 1. 容量：\(c(u,v)\)表示边最大允许的容量 2. 流量：\(f(u,v)\)表示一条有向边中已经占用的流量 3. 剩余流量：\(c(u,v)-f(u,v)\) 4. 残量网络：原图基础上，添加每条边的反向边构成残量网络 5. 增广路：在残量网络中，一条从原点到汇点

题目链接 分层图模板题 一开始写了一个 dp ，\(f[i][j]\)表示第\(i\)个点用了\(j\)次的最小值。 \(f[i][0]\)是不用免费机会，跑一次单源最短路就可以预处理。 在图上枚举转移，每次无非就是选和不选两种决策。 感觉挺对的，然而不知道怎么 WA 了... 发现这个枚举转移好像很笨，因为可以在最短路时顺便处理出来。 建立分层图\(u,j*n\)向\(v,(j+1)*n\)

题目链接 设\(f[i]\)表示凑成\(i\)的方案数。 枚举所有\(f[i-2^k]\)加上是错误的，因为有些方案可能会重复。 比如现在要凑\(7\) 有可能从\(5=1+2+2\)或者\(6=2+2+2\)转移过来。 显然是重复了。 正确的姿势是做完全背包，也就是交换一下枚举顺序... 把\(2^k\)当作物品凑\(i\) 123456789101112131415161718192021

题目链接 因为要求完全图的最小生成树是给定的\(T\)，那么与树边等效的边边权都要大于树边。 考虑在求最小生成树的过程中，合并两个点集，除了树边的两个端点，两两直接都要连一条权值为\(w+1\)的边。 123456789101112131415161718192021222324252627282930313233#include <bits/stdc++.h>using name

题目链接: luogu 最优化两个目标，好像不太好处理。 可以先转化一下，求被两盏灯同时照亮的边数应该尽可能大，就等价被一盏灯照亮的边数应该尽可能小。 假设放了\(x\)盏灯，被一个灯照的边有\(y\)条，那么可以设计一个目标函数\(g=Mx+y\)，让\(g\)尽量小。\(M\)是什么？可以想到\(M\)是一个比较大的数，因为要让\(x\)的个数对目标函数的大小起决定性作用，可以证明\(M\

题目链接 花一上午学了下这个东西,记录一下方便以后复习,以下主要靠抄OI-Wiki ## 题目 给定\(n,a,b,c\).计算: \[ f(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor \frac{ai+b}{c} \right\rfloor \] \[ g(a,b,c,n)=\sum\limits_{i=0}^ni\left\lfloor \frac{a

写这种题先写一下暴力的\(dp\)式子. \(dp[i][k]=min(dp[j][k-1]+w)\). 可以发现决策是具有单调性的,其他题解说得都很清楚了. 那么就可以用分治来优化这个方程. 因为是分层的复杂度是\(\mathjaxcal{O}(nlogn)\). 123456789101112131415161718192021222324252627282930313233343536373

构造。 因为四元组最大公因数是\(k\)，所以将四个数同时除以\(k\)，得到的四个数互质。 所以构造出四个互质的数就可以了。 设第一个数是\(x\)，因为四元组尽量小，所以构造的数要尽量接近。 显然只能有一个偶数，所以很容易得到第二个数是\(x+1\)，第三个数是\(x+2\)，并且\(2\nmid x\)。 第四个数不能是\(x+3\)，因为只能有一个偶数。那么可不可以是\(x+4\)呢？ 我

三元环个数 可以看看这篇文章不常用的黑科技——「三元环」 给每条边定向，度数不同的大度数向小度数连边，度数相同编号小的向大连边。 这样会生成一个有向无环图。 直接搜索每个点\(u\)的相邻的点，打上标记是被谁(u)访问的。 搜索每个点相邻的点的相邻点，如果某个点被\(u\)访问过了，说明这是一个三元环。 因为每个三元环都长这样 >[图片来源]((https://www.luogu.com.