A-FlowProblemHDU3549FlowProblem题解：网络流版题，甚至今天早上我还只会EK（辛亏卡EK的没那么多，但是还是被迫学习dinic）B-WarHDU-3599War题意：求1到n最短路径（无向边）的最大条数（一条边不能重复经过）题解：题面就让人难懂，好像出题人在考生活实际和理解能力。看懂题就简单了，先跑

T1（批量式kruskal，增量式的nb应用）ABC355F.这题边权巨小。只有10。考虑从此处下手。这里考虑kruskal的过程，我们一开始的想法是，不断加权值最小的边，但是这里显然有冗余，我们没有必要一个个取吧？考虑一次把x边取完。也就是开10批，当然开并查集维护连通关系，也就是维护出这10个并查集。对于

link一道比较深刻的题目。考虑条件相当于：对于任意\(1\)的个数有限的\(S\)，其所有的长度为\(2k+1\)的子串，经过\(p\)的映射后\(1\)的个数不变。统计所有的长度固定的子串信息，我们有一个trick：对于一个长为\(2k+1\)的二进制串\(w\)，设其前\(2k\)位和后\(2k\)位组成

E将所有的下标作为点，建一张无向图。当且仅当可以询问\([l,r]\)时，在点\(l\)和\(r+1\)之间连一条边。可以发现能求出\([L,R]\)的和等价于\(L\)与\(R+1\)连通，且最少询问次数等于两点间最短路径边数。具体实现是容易的。F边权很小，提示我们可以暴力枚举和替换边。开

在一张有向无环图DAG中，有边权，给定起点点集A，终点点集B，且A,B中的点数一致。定义P表示DAG中的一条路径。定义w(P)表示路径P上的边权乘积。定义e(a,b)表示a到b的所有路径的边权乘积之和，即\(e(a,b)=\sum_{P_i\in(a\tob)}w(P_i)\)定义一组A到B的不相交路

F-MSTQueryProblemStatementYouaregivenaweightedundirectedconnectedgraph$G$with$N$verticesand$N-1$edges,whereverticesarenumbered$1$to$N$andedgesarenumbered$1$to$N-1$.Edge$i$connectsvertices$a_i$and$b_i$withaweight

很久没有见到这么好的题了。原题面用ChatGPT

分层图思想分层图在最短路中经常用到。直观上讲，就是将一个图复制k倍，互相是平行的，即互不影响，分层图两两之间会有决策边相连。这就等价于要在一个图上进行k次决策，对于每次决策，不影响图的结构，只影响目前的状态或代价。一般将决策前的状态和决策后的状态之间连接一条权值

CF1085DMinimumDiameterTree题解比较水的一道绿题观察样例可以发现，边权都平分在叶子节点唯一的一条连边上，由此猜到联想到可以把贪心地将边权全部平均分配到这些边上，这样写出来就能AC了。如何证明先来一张图方便理解：利用反证法：假设按上述做法分配边权后可以至少修改一次

\(\mu\)取值即所选边权的中位数。把每条边拆成两条（黑边和白边），边权分别为\(\mu-w_i\)和\(w_i-\mu\)，要求黑边和白边各选\(\left\lfloor\dfrac{n-1}2\right\rfloor\)条，求最大生成树。可以直接wqs二分，时间复杂度\(\mathcalO(nm\logw~\alpha(n))\)。把所有边的边权

题目大意：一张无向完全图，节点\(i\)的点权为\(a_i\)。每条边的边权由一个函数给出，\(W(u,v,t)=a_ua_v+t\times(a_u+a_v)\)，其中\(t\)是一个尚未确定任意实数，且对于所有边都是一致的。显然如果固定\(t\)就存在一颗最小生成树，于是定义\(F(t)\)等于此\(t\)下最小生成树的边权

BFS在最优性问题中，状态按照非最优化属性进行分组，且每个分组存在且只需要保留最优状态。一般最优性问题分为\(2\)种，边权为正数、边权为非负数。边权为正数且相同这种情况，转移时最优化属性的值会变得更劣，每次转移时最优化属性的值会变劣最小单位。而最优化属性有拓扑序，可以按

题目传送门：https://www.acwing.com/problem/content/241///懒得手敲题目先给一下题解：#include<iostream>#include<unordered_map>//这个题目有两个点要想明白，一个是点到根的距离标志着这个点的性质，且在路径压缩的过程中此点不会改变//第二点就是在出现新的关系，也就是要将两

首先建立一个超级点\(S\)，对于每一个可以充电的点\(u\)都建立一条从\(S\tou\)的边权为\(0\)的有向边。从这个超级点\(S\)开始跑一遍最短路算法，就可以得到每一个点\(u\)至少需要花费多少的电量才可以走到一个充电点。令\(D_i\)表示\(i\)号点最少花费多少可以到一个

2024-04-09mushroom勾石线段树题，4个lazytag考场上会了，但是写出来第二个样例一直过不去发现每次询问全部从根pushup一遍就对了，于是超时拿到了30分的好成绩考完试对着aqz的代码改了一下午，发现一模一样，一直看不出错好心的aqz帮我看了看，2min就看到我有一个lft写成

把一条边\(w\)写成\(wx+1\)，则生成树边权积的一次项就是答案。求逆：\((ax+b)^{-1}\equiv(-\frac{a}{b^2}x+\frac{1}{b})\pmod{x^2}\)Codeusingll=longlong;constintN=31;constintMOD=998244353;structPoly{ lla,b; Poly(lla=0,llb=0):a(a),

ABC218EDestruction题解题意给你一个\(n\)个点\(m\)条边的带权无向联通图，你可以删去任意条边，要求保证图联通的情况下删去边的权值和最大。\((n\le2\cdot10^5\,\m\le2\cdot10^5\,\-10^9\lee_i\le10^9)\)(\(e_i\)为边权)分析首先我们考虑边权全为正的情况，那么我们删

生成树学习笔记代码合集很好，这还是一篇复习笔记。考虑这么一个问题，给出一张无向图，有\(n\)个点，\(m\)条边，边有边权，要你找\(n-1\)条边，使得这\(n\)个点联通且边权和最小。Kruskal首先，我们先把边权进行排序，然后贪心的加边，把选的边所带的点加到一个集合里面。如果\(x,y\)

最小生成树学习笔记代码合集很好，这还是一篇复习笔记。考虑这么一个问题，给出一张无向图，有\(n\)个点，\(m\)条边，边有边权，要你找\(n-1\)条边，使得这\(n\)个点联通且边权和最小。Kruskal首先，我们先把边权进行排序，然后贪心的加边，把选的边所带的点加到一个集合里面。如果\(x

前言考虑单源最短路的一个性质：在有向图中，若存在边\(u\tov\)，边权为\(w\)，则\(\mathit{dis}_u+w\ge\mathit{dis}_v\)。正确性是显然的，因为如果反之\(\mathit{dis}_u+w<\mathit{dis}_v\)，我们就可以令\(\mathit{dis}_v\gets\mathit{dis}_u+w\)，原先的就不是最短路了，与题设矛盾

P1967[NOIP2013提高组]货车运输原题地址思路：由于题目要求的是使两点之间的最小边权最大，所以可以构造最大生成树（最大生成树一定是最大瓶颈生成树，而瓶颈生成树上两点之间的路径，在原图中的所有路径中，最小边权仍然最大，即满足题目要求，详见https://oi-wiki.org/graph/mst/#性质），

环的权值为边权最小值，可以想到从大到小遍历权值，如果一条边加入后出现了环说明这条边的边权就是整个环的权值。类似Kruskal，我们把边权从大到小排序，然后用并查集维护连通情况，算出最小的权值。然后跑dfs找环输出方案。时间复杂度\(\mathcal{O}(m\log{m}+n)\)。#include<bits

MinimumSpanningTrees给定一张\(n\)个点的完全图，每条边有\(p_0\)的概率不存在，\(\forall1\lei\lek\)，有\(p_i\)的概率边权为\(i\)，求所有可能总权值的概率.\(n\le40,k\le4\)数据严重偏小了似乎.\(f_{i,j,k}\)表示权值为\(1-i\)的边，\(j\)个有标号点组成的权

借这一道题目来介绍一下最小瓶颈路和Kruscal重构树首先本来这道题目我其实是没看出来是最大生成树的（因为不知道上面两个东西），然后我想的是二分，当然也可以做，但是复杂度多一个\(log\)对上面两个东西的介绍见OI-wiki下面是一些解释最小瓶颈路的性质的第一句话说“根据最小生成树定

给定一颗包含n个顶点的树，第i条边连接u[i]和v[i]，边权为w[i]。记f(i,j)表示顶点i到j的简单路径上边权的最大值，求$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}f(i,j)$。2<=n<=1e5;1<=u[i],v[i]<=n;1<=w[i]<=1e7对于每条边，考虑以它作为最大边权的路径数，为两侧节点数的乘积，数点可以用并