题意给定一个有向图\(G\)，以及将所有边反向重连的无向图\(T\)。你最多可以在\(T\)上连续走\(k\)条边，走过每条边的代价都为\(1\)，然后必须在\(G\)的对应点上走一条边以恢复体力。若当前对应点没有出边，则停留在该点\(1\)代价。求每个点到\(n\)的最小代价。Sol考

最大流对于网络\(G=(V,E)\)，给每条边指定流量，得到合适的流\(f\)，使得\(f\)的流量尽可能大。此时我们称\(f\)是\(G\)的最大流。Dinic算法思想考虑在增广前先对\(G_f\)做BFS分层，即根据结点\(u\)到源点\(s\)的距离\(d(u)\)把结点分成若干层。令经过\(u\)

本文首发于QOJhttps://qoj.ac/blog/skip2004/blog/866大家好，我是钱哥，我来写一下PKUSC2024最短路径的题解。没有做过这个题的同学可以先自行做一做。我们下面来讲解一下如何一步步解决这个题目。subtask4首先，我们来解决第一个具有挑战性的子任务：\(m\leq2.5n\)，这个点具

\(\color{red}(1)\)P2296[NOIP2014提高组]寻找道路在有向图\(G\)中，每条边的长度均为\(1\)，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：路径上的所有点的出边所指向的点都直接或间接与终点连通。在满足条件\(1\)的情况下使路径最短。

这道题目实在没有什么好的办法去描述状态空间，只能感性理解一下，等对概率的理解更深了再来吧。。。发现这是一道概率DP，而且满足拓扑序，我们直接倒序转移就好了设\(f_i\)表示从第\(i\)个点到第\(n\)个点的概率，我们发现当只有一条出边是非常好转移的，但是其他就不太行了我们遇到这种

这道题目本身不算难，只是有一点点小的最短路算法的改动我们首先从分层图的角度考虑这个问题，每一层代表一秒钟在第一层，最开始只有\(1\)在集合中，然后我们扫描第一层中\(1\)的所有出边，将终点全部加入到集合中在第二层，我们扫描集合中所有点在第二层中的出边，把不在集合中的终点全部加

欧拉回路感觉自己学了个假的欧拉回路。trick1给定一个图，我们需要给每个边定向，使得每个点入度与出度差不超过\(1\)。\(sol:\)首先，因为有奇数点的存在，我们不能直接构造出欧拉回路。所以我们建立一个虚点，然后从所有奇数点和虚点连边，显然此时所有点度数都为偶数，我们跑欧拉回

当给定一张图后，我们需要存储。下面有三种存储方法。1.邻接矩阵直接用二维数组\(g_{i,j}\)来表示从结点\(i\)到结点\(j\)的距离。空间复杂度为\(\mathcal{O}(N^2)\)。2.邻接表可以发现，邻接矩阵在存稀疏图时，有大量的空间浪费。此时可以使用邻接表存图。邻接表就是对

某人竟然忘记了星期天晚上有\(\text{ARC}\)，我不说是谁。首先选择最小点删除和最小字典序都是最小化，所以可以弱化最小点删除的限制，现在原问题就变成了可以删除任意一个点的出边，如果没有出边则为\(0\)(这个其实本题中是最优的策略)。如果每一个点向其删除的出边连边，先考虑它会形

恶魔的低语，会送来天堂的福音。题意有一个\(n\)个点的有向无环图，第\(i\)（\(1\lei\len\)）个点有mi条有序的出边\(e_{i,1},e_{i,2},...,e_{i,m_i}\)。每个点要么是黑点，要么是白点。有\(k\)个程序，第\(i\)个程序形如从\(r_i\)开始，对\(r_i\)的直接或间接后继

Boruvka最小生成树一个用得相对少的最小生成树算法。需要注意的是只能做边权互不相同的问题。怎么做？首先先将所有点看做独立的连通块。然后对于每个联通块找到最小的一条出边，判了连通性，可以就直接合并就行了。这样每次联通块个数每次都会变为原来的\(\frac{1}{2}\)，所以只

纪念一下第一次补完div1的所有题这个1E相较于其他的1E并不算太难。本题解部分参考官方题解。先观察到一条边是好的当且仅当它的值和一个端点的值相同。原因很简单，要求两端点值不同，若边权跟点权也不同，那么三个值分别只能为\(1,2,3\)，又因为\(1\oplus2\oplus3=0\)，不符

洛谷传送门考虑dp，设\(f_i\)为以\(i\)结尾的合法子串个数。如果我们能对每个\(i\)，求出来\(g_i\)表示最大的左端点\(l\)使得\([l,i]\)是合法串，那么\(f_i=f_{g_i-1}+1\)。若\(g_i\)不存在则\(f_i=0\)。答案为\(\sum\limits_{i=1}^nf_i\)。考虑求\(g_

考虑给无向图定向，设\(d_u\)为点\(u\)的度数，对于无向边\(\langu,v\rang\)，若\(d_u<d_v\)或\(d_u=d_v\)且\(u<v\)，我们在新图中连有向边\(\langu,v\rang\)，否则连有向边\(\langv,u\rang\)，容易发现新图必然是一张DAG。我们枚举三元环中的一个点\(x\)，在新图中同时标记

T1大水题，用位运算更加便捷求解。T2看出来有环了，但是没往基环树上想，寄。暴力分，有部分分是基础树，可以跑一遍深搜，根节点的选择是k种颜色，剩下的是k-1种颜色。还有暴力是可以二分图染色做出来的。正解，我们对于一个环上的操作，可以用递推式子求出来。f[0][i],f[1][i]分别表

这是之前关于欧拉路的两篇博客。关于欧拉路的逆序压栈问题：here。22年写的一个小总结：here。关于欧拉路，主要疑点在于两个：一是压栈输出的原理；二是打上标记后时间复杂度退化的问题。压栈输出的原理走到点u时，有两种情况：u此时是终点，那么没有没走过的边与之相连。u此时不是终点

概述定义基本规则：两个玩家轮流移动同一颗棋子。每次移动沿一条出边将棋子移到下一个点。当前玩家走不了（没有出边）时输。图可能有环，游戏无法结束时为平局。出现平局的根本原因是决策会绕起来成环。我们先来解决如何判断一个点的胜负状态。首先，如果图是\(\text{DAG

一、什么是决策树决策树（DecisionTree）是有监督学习中的一种算法，并且是一种节本的分类与回归的方法。即决策树有两种：分类树和回归树。那什么事决策树了？简单点说就是二元判定，从头到尾逐次判定其归属类型。从上述案例，我们很容易理解：决策树算法的本质就是二元判定的属性结构，我们

1.1什么是有向图dp我们遇到的博弈问题，例如【省选联考2023】过河卒，很多都是转化为有向图博弈，其形如：一些节点为终止节点，状态已经确定；一个点的状态由其出边所到达点的状态确定。如果是DAG上，显然我们可以按照拓扑序让每个点搜索到的时候其所有出边都已经确定了状态。但是题目有

严谨一点讲，这叫广义串并联图方法，即：删一度点，缩二度点，叠合重边。通俗一点讲，叫：把看上去显然的情况做掉答案就出来了[USACO22OPEN]HoofandBrainP按照套路，先考虑没有出边

IOI2022鲶鱼塘(2)记第\(i\)列的堤为\([0,l_{i}),\)贡献区间为\([l_{i},r_{i}]\)，则限制即\(l_{i}>r_{i}\)或\(r_{i}<\max(l_{i-1},l_{i+1})\)若\(l_{i}>r_{i}\)或\(r_{i

独木舟可以看作将边定向，并在每次经过后反向，要求最终每条边方向不变在此基础上，考虑以下两种情况：对于出度为\(0\)的点，到达其后仅能原路返回，不妨删除若起点出度为\(1\)

[复习资料]最小树形图最近在整理自己的模板集，然后就发现了最小树形图这个基本不考的考点，我记得当时学最小树形图的时候都是迷迷糊糊的，跟着题解敲了一遍代码，根本无法理解这

作者：京东科技王军前言Gemini是目前state-of-art的分布式内存图计算引擎，由清华陈文光团队的朱晓伟博士于2016年发表的分布式静态数据分析引擎。Gemini使用以计算为中

Dijkstra用pair实现$edge$（struct）建立edge数组$E$来记录每个点的出边$pair<int,int>$（struct）用来给优先队列服务，$first$为$dis[u]$,$second$为$u$初始化：$dis[u]=