换根DP（二次扫描DP）

介绍

对于树形DP,若给定无根树，而问题的最优解与根节点相关，那么考虑换根DP。

通常可以将枚举根节点跑DP的时间复杂度由 $O(N^2)$ 降为 $O(N)$。

赛前训练2-连通性系列问题——总结

A

洛谷P2656

错误原因

double 的精度不够，应开 long double。

正解

1. 条边只有在环上时，才可能多次经过，且一定会经过足够次直到边权为 $0$；
2. 输入时维护 x[i],y[i],w[i],kw[i] 其中 kw[i] 表示第i涤边迭代经过的总边权和；
3. 缩点建新DAG图，跑最长路。

1931年9月18日

震惊中外的九一八事变爆发

白山黑水间，中国人民奋起反抗

揭开抗战14年的序幕

也成为世界反法西斯战争的起点

阅读全文 »

最小割问题

对于给定的网络流模型，其最小割是指删除边权和最小的边集，使得 $s$ 到 $t$ 不连通。

最小割等于最大流，因为增广路的流量限制是由这些权值的边，方案不一定唯一。

状压DP（二）

洛谷P3092

P3092 [USACO13NOV] No Change G

这道题，我们一般定义 $dp_{i,j}$ 为硬币使用了二进制下的 $i$，付到第 $j$ 个人的最多剩下多少钱。

不过 $2^{16}\times 10^5=6,553,600,000$，会超过空间限制。

我们发现“最多剩下多少钱”没有用，因为可以通过使用情况算出。

定义新的状态 $dp_{i}$ 表示硬币使用了二进制下的 $i$ 的最多能付到的人，可以通过前缀和加二分优化计算。

状压DP

状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

——OI-WIKI

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

二分图

若一张无向图 $G$，可以将所有的点分成 $2$ 个点集，且 $2$ 个点集内部没有连边，那么称 $G$ 可以划分为一张二分图。

• 注意：二分图的划分不一定唯一，且不一定连通。有向图在实际问题中，也可以划分一分图

二分图存在的充要条件

• 没有奇环

二分图的判定

染色法，任意选择没有访问的点开始 dfs，并且 $0,1$ 交替染色，只要出现一条边的 $2$ 个端点颜色相同，那么就不是二分图。

区间DP

• 是一类子问题从短到长，而不是从左到右的动态规划问题。

状态

一般是：$dp_{i,j}$ 表示将区间 $[i,j]$ 的元素合并、拆分的最值、方案数。

转移

1
2
3
4
5
6
7

for (int len = 2; len <= n; len++)//这问题
	for (int i = 1; i + len - 1 <= n; i++)//状态
	{
		int j = i + len - 1;
		for (int k = i; k < j; k++)//决策点
		dp[i][j] = 运算(dp[i][j], 状态转移方程);
	}

区间dp（三）

洛谷P1880

P1880 [NOI1995] 石子合并 - 洛谷

石子在圆形操场的四周摆放，直接当没有环形区间dp显然会少答案。那么我们一定要这么做怎么办？少了的话可以加回来，斩环为链，数组多一倍，再区间dp。

$dp_{0/1,i,j}$ 表示区间合并 $[i,j]$ 的最小/最大值。

答案为 $\displaystyle\min_{1\le i\lt n}^idp_{0,i,i+n-1}$ 和 $\displaystyle\max_{1\le i\lt n}^idp_{1,i,i+n-1}$。

$\displaystyle dp_{0,i,j}=\min_{i\le k\lt j}^k\left(dp_{0,i,k}+dp_{0,k+1,j}+\sum_{i\le l\le j}^la_l\right)$，$\displaystyle dp_{1,i,j}=\max_{i\le k\lt j}^k\left(dp_{1,i,k}+dp_{1,k+1,j}+\sum_{i\le l\le j}^la_l\right)$。