状态压缩模板题目链接：https://www.luogu.com.cn/problem/P1433说明：dp[s][j]表示的是含有j号点的s集合，以j号点为终点的最小旅行商距离！那么dp[s][j]=min(dp[s][j],dp[s^(1<<j)][k]+dist(j,k));其中：dp[s^(1<<j)][k]指的是去掉s中的j号点，并且以k为终点的距离！记忆并理解#inc

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。所有边的长度都是 1，点的编号为 1∼n。请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。输入格式第一行包含两个整数 n 和 m。接下来 m 行，每行包含两个整数 a 和 b，

C先预处理出三个数组能拼出的数，存放到map中。查询的时候只需要看这个数是否出现在map里即可。时间复杂度\(O(n^3\logv+Q\logv)\)，\(n\leq100\)，\(\logv\)是map的时间复杂度。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=3e

其实这个对偶图的定义有点问题，正确的：所以PPT画的对偶图也有点问题，还要在\(4\)号点上画一个闭环（之后的图没有做修改）这个证明唯一想不明白的就是为啥紫色的边一定会构成一棵树，主要是无法判断是否连通

这道题目真实绝了，这篇随笔主要是对蓝书上面的注释首先那个结论肯定要知道，然后选取\(1\)号点作为基准点也是想到了的那么接下来肯定就是把\(1\)号点所在连通块当做树根嘛，问题是怎么去分配剩下的点我最开始想的是像树形背包一样去DP，但是不知道具体有多少子树，然后我又想枚举子树个

/*反向考虑，反向建图，考虑从x号点出发，可以到达哪些点，我们从n~1开始枚举如果某一个点被更新到，呢么这个点一定不会被后面的点更新，就直接可以标记掉，从n号点出发可以到达5号点，呢么从n-1号点出发就可以直接跳过5号点，还有5号点能到达的点。复杂度是O(n)，这样的想法很常见*/#include

最小生成树概念给定一个无向图，在图中选择若干条边把图的所有的节点连接起来，要求边长之和最小。在图论中叫做最小生成树。Prim算法Prim算法生成最小生成树的过程基于贪心思想，每次将距离已经连通部分最近的点和对应的边加入连通部分，使得连通部分逐渐扩大，最后将整个图连接起来并

讲解  模板 第1题    bellman-ford练习查看测评数据信息给定一个n个点m条边的有向图，图中可能存在重边但不存在自环，边权可能为负数。请你求出从1号点到n号点最短距离，如果无法从1号点走到n号点，输出impossible。1≤n≤500，1≤m≤10000，任意边长的绝对值

第3题   有边数限制的最短路查看测评数据信息给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。请你求出从1号点到n号点的最多经过k条边的最短距离，如果无法从1号点走到n号点，输出impossible。注意：图中可能存在负权回路。1≤n,k≤500，1

算法基础 模板题 第1题    spfa最短路练习查看测评数据信息给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出impossible。数据保证不存在负权回路。1≤n,m≤100000

最短Hamilton路径状压dp。设\(f_{S,i}\)表示走过的节点状态为\(S\)\((0\)为没走过，\(1\)为走过\()\)，当前在点\(i\)时的最小代价，显然\(S\)的第\(i\)位必须为\(1\)。那么\(f_{S,i}=\min_{S\operatorname{and}2^j=1,j\neqi}\lbracef_{S\operatorname{xor}

Description有\(n\)条河和\(m+1\)个交汇处构成一棵以\(0\)号点（即大海）为根的树。每条河有各自的名称。对于一个交汇处，从它流出的干流的名称是流入这个交汇处的各个支流的名称之一。一条河流的长度是以它为名称的河流的长度之和。对于一个可能的命名方案，一条河流的排名等于

换根树形动态规划考虑以1为根的情况,size[i]表示以i为根的子树中有多少个点,f[i]表示考虑以i为根的子树,i到子树其他所有点的距离的和;假设j是i的儿子,以j为根的子树对f[i]的贡献为f[j]+size[j]\[f[i]=\sum_{j\inson(i)}(f[j]+size[j])=\sum_{j\inson(i)}(f[j])+size[i

CF838D AirplaneArrangements题目传送门很高妙的题。直接计算不太好做，考虑把链首尾接起来拼成环，但注意到直接拼就无法判不合法，所以在$1$和$n$中间插入一个$n+1$号点，若$n+1$号点被覆盖则不合法。考虑对于所有方案计算$n+1$号点被覆盖的概率，注意到任意一种覆盖情况

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。输入格式第一行包含整数 n 和 m。接下来 m行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y的

\(CCPC2022\)广州\(I\)这是一道和队友\(vp\)时我没有出的\(dp\)题目，说明我的\(dp\)还有很多空缺，加练！题意一种高度繁殖的细菌感染了一棵由\(n\)个节点（有\(n-1\)条边，无循环）组成的树。这些节点的索引从\(1\)到\(n\)。一开始正好有一个节点被感染。树上的每个节点都有一个初

具体题解可以看zhy136036那一篇解释一下是如何合并树的每次都可以提取出来一个子树然后把这三棵子树重叠在一起（根对根，2号点对2号点，以此类推），就得到了这个新图然后解释一下为什么这么做是对的首先在单次操作中，至少需要把这个新树给遍历完，不然的话就会存在有些点遍历不到，即这是

首先我们抽象一下这道题的模型，然后把引理记住模型：对于一棵树上选定的一些点，把他们连通起来的最小边数我们先考虑一种朴素做法，对于任何一种方案，任取其中两个点，那么这个方案一定包含这两个点之间的路径就是说，我们依次添加每个点，对于每一个新添加进来的点，让这个点与其已经添加的点

题目传送门description给定\(n,k\)，求\(n\)个点的无向完全图满足其边权为\([1,k]\)中的正整数且其最小生成树边权和等于与1号点相连的边的权值和。\(n,k\leq250\)solution不妨先确定1号点到剩下\(n-1\)个点中\(i\)号点的边权为\(a_i\)。可以发现，对于其他每条

题目链接120.三角形最小路径和解题过程我觉得这道题已经可以当作如何优化动态规划的经典例题了，首先从路径上采用的是从上到下的方式，我是用了我自己能想出来的方法，也就是二维数组去解决的，接下来进行优化，将O(n2)的空间复杂度降低为O(n)，使用2n的空间存储状态，接下来再次进行优化，

JOISC2018Construction题目链接Statement给定$n$个点，初始时$i$号点的权值为$c_i$。接下来进行$n-1$次加边操作，每次连接一条边$(u,v)$，保证此时$u$与$1$号点连通，$v$与$1$号点不连通。对于每一次加边，求出$1$号点到$u$的简单路径上的逆序对数量，并在操作结束

Description策策同学特别喜欢逛公园。公园可以看成一张\(N\)个点\(M\)条边构成的有向图，且没有自环和重边。其中\(1\)号点是公园的入口，\(N\)号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。策策每天都会去逛公园，他总是从\(1\)号点进去，从\(N\)

1.题目洛谷传送门2.思路我们可以把不确定的点当成真实存在的\(0\)号点，建边的时候就正常连即可。然后我们来看一个样例：1-2-03-4-5当我们把\(0\)号点看成\(3\)号点时，答案就是\(1\)号点到\(0\)号点的距离加上\(3\)号点到\(5\)号点的距离。然后我们再

今天就返校力

Problem题目概述给你一个无向图，边权都为\(1\)，求：离\(1\)号点最远的点的编号、最远的距离、有几个点是离\(1\)号点最远的。思路直接用：优先队列\(BFS\)，先求出\(1\)号点到每个点的最短路，存到\(dis\)数组中，然后再求\(max(dis[i])\)，就搞定了。错误原因审题&做法错