多校A层冲刺NOIP2024模拟赛03T1五彩斑斓（colorful）签到题直接暴力枚举是\(O(n^4)\)，考虑使用\(bitset\)优化，对每个点开个\(bitset\)，预处理它所在一行它及它之前相同颜色的位置，这样就只用枚举另一个点所在列，时间复杂度为\(O(n^3+\frac{n^4}{w})\)。T2错峰旅行（travel）

一道很好的手玩题，被薄纱了。首先判掉\(\foralli,p_i=i\)的情况（显然是\(n\)）然后考虑按照\(p_i\)连边，先构造每一个环的方案。发现可以简单放置两面镜子使得\(i\)射到\(p_i\)，而且只要从高到底构造，一定不会产生影响。但是每一个环的最后一个点很特殊，因为第1个点下面放置了让第1个

二分图定义如果你能把一个图划分成两个集合，集合内部的点没有边相连接，那么这个图就是一个二分图，如图就是一个二分图：交错路：从一个没有被匹配的点出发，依次走非匹配边，匹配边，非匹配边……最后到达另外一部点当中某个没有被匹配的点的路径。增广路：从一个没有被匹配的点出发，依次走

​本题是CSP-J组的第四题。题意：给出一个有向图，当前在1号点，初始在时间0，必须在k的倍数的时间出发，且到终点的时间也必须是k的倍数。每条边有一个边权，只有在当前时间≥时才可以通过，且不能在原地不动，即每一个时间点必须走一条边。问从11号点出发到nn号时最早的时刻。（没

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

RoadoftheKing题解形成强连通图的必要条件是点\(1\)能在环中，于是考虑\(1\)号点形成的强连通分量\(x\)。这类图论计数题目往往考虑dp，于是我们设\(dp_{i,j,k}\)表示走了\(i\)步，经过了\(j\)个点，\(1\)号点形成的强连通分量\(x\)的大小为\(k\)时的方案数。转移

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

迪杰斯特拉（Dijkstra）算法是一种用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。它是由荷兰计算机科学家艾兹格·迪科斯彻（EdsgerDijkstra）在1956年提出的。Dijkstra算法适用于处理带有非负权重的图。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法，每次遍历到始

//105判断图是否同构.cpp:此文件包含"main"函数。程序执行将在此处开始并结束。///*http://oj.daimayuan.top/course/14/problem/600给你两张无向简单图，保证两张图的顶点数和边数相同，请判断这两张图是否同构。如果同构输出Yes，否则输出No。输入格式第一行两个整

凸多边形k划分计数给定\(n,k\)，求凸\(n\)边形划分成\(k\)个不相交部分的方案数。sol先引入一个定理：Raney定理：和为\(1\)的整数序列的所有循环位移序列中有且仅有一个满足任意前缀和大于0。证明可以考虑任取一个循环位移序列，然后求前缀和，找到最靠右的前缀和最小的位

图论差分约束有\(

目录Dijkstra迪杰斯特拉算法写法时间复杂度例题描述输入描述输出描述样例输入用例输出用例写法Spfa算法例题描述输入描述输出描述样例输入用例输出用例写法Bellman_Ford算法(贝尔曼-福特算法)写法例题描述输入描述输出描述样例输入样例输出样例

考场上被这道题卡了三个半小时，没想到自己的构造水平这么差……正解是，字典序最小的必要条件是1号点连的边尽量多，相同时2号点连的边尽量多，相同时3号点连的边尽量多，以此类推构造题的核心在于数学推导而不在于代码实现一步步优化得到正解似乎是可行的，但耗时太长；这次你推导3个多小

这道题目看官方题解就好了，这个转换图论挺显然的证明一下为什么最后一定是显然练完贬值后图只能长成这个样子在消掉长度为\(2\)的环后，如果说图没边了，那么显然就不用交换了，否则的话我们任取一条边那么对于\(2\)号点来说，要么没出边，要么出边的终点是\(3\)号点（因为没有长度为\(2

状态压缩模板题目链接：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}