Prim的模板 用最困难的地方就是如何存边，我们可以用链式前向星存图，因为这个就是存的边，在结构体中多维护一个边的编号就好了 代码 #include <bits/stdc++.h> #include <unordered_map> #define endl '\n' #define int long long const int maxn = 2e6 + 5; const int inf = 1e18; int dis[maxn], vis[maxn], head[maxn]; int cnt = 0; struct Edge { int u, v, w, nx...

思路 Dijstra做法 + 链式前向星建图 重边没有影响，正常建图就行 代码 #include <bits/stdc++.h> #define endl '\n' #define int long long const int maxn = 2e6 + 5; const int inf = 1e18; int dis[maxn], vis[maxn], head[maxn]; int cnt = 0; struct Edge {     int u, v, w, nxt; }edge[maxn * 2]; int n = 0, m = 0, s = 0; void A...

ZT6 小红的字符串构造 这是题面 构造 思维 思路 不用想得很复杂 可以看成一个匹配问题，每一个字符要和一个与自己不同得字符匹配，而且每一个字符都要匹配，每一个字符都要被匹配到 我们可以先用一个集合统计有多少种字符 ,让所有字符都被匹配到，一种简单得方式就是每一个字符和它右边的字符匹配, 最后一个和第一个匹配，例如 最后别忘了特判不行的情况，也就是只有一种字符的情况 代码 #include <bits/stdc++.h> #define endl '\n' #define int long long // 可以看成构造一个匹配，每个字母要和一个非自己的字符匹配 // 如何判断不...

牛客多校第六场反思 D. Puzzle: Wagiri 题目大意 给定一张简单连通无向图，边有黑白 移除任意一条边使得图仍然连通，且黑边都在环上，白边都不在环上，或者输出无解 思路 黑边的环在一开始就存在了 可以先不看白边，反正是可以移除的 把黑边缩点，然后用一个把割边去掉，再用白边连就好了，白边不够就无解了 注意：这里割边也是要删除的边 对白边的处理：如果连接白边的两个点都连了同一个边双，那这个白边就不能再被用了，否则就可以用它来连，就有一条白边可以用了 具体的步骤： 对黑边求一个边双连通分量，然后把割边去除 可以用并查集把所有点连起来，最后删边剩下的结果应该也是之剩下一个连通块 ...

牛客第九场反思 K. kill The Monsters 题意概述 有个怪兽,每个怪兽血量为 有两种操作： 使得所以的怪兽的血量减少1 使得某一个怪兽得血量变成 是给定的 问最少操作次数 思路 最主要的问题就是到底使用哪一种操作 可以这样想：让某一头怪兽成为基准，大于这个基准的进行操作二变得小于等于这个基准，然后结果就是次数加上基准的血量。这样尽可能的让每一次操作贡献最大 那么让哪一个成为基准呢？肯定是让结果最小的那个成为基准 首先肯定能求出来一个最大次数，这个是我们能够接受的上限 可以尝试让每一个成为基准看哪一个会使得结果最小 很难算好像，但是如果基准在最前面就好了 我们可以将所...

割边(Tarjan) 题意概述 一个图，个点，条边，求这个图的割边 思路 : 点是第几个访问的 : 从点出发经过任意条树边，最多一条返祖边，最多一条横插边能回到值最小的那个点 对于，如果, 那么就是一条割边 这里有一个需要和求割点不一样的地方-----返祖边返到了自己的爸爸会发生什么？ 如果这个时候继续更新，那么上面那个式子永远不会成立，那么就没有割边了 用一个pre数组记录每个点在书中的前驱节点 代码 #include <bits/stdc++.h> const int maxn = 200; std::vector<int> mat[maxn]; int n =...

点双连通分量（Tarjan） 题目概述 对于一个 个节点 条无向边的图，请输出其点双连通分量的个数，并且输出每个点双连通分量。 算法主要步骤 维护一个栈 第一次访问某一个点时，将其入栈 当割点判断的法则成立时，即= dfn[fa]&preview=true">时，不断从栈中弹出节点，直到被弹出，这些被弹出的点和一起构成一个点双连通分量 思考 对于一个点双，它在 搜索树中 值最小的点一定是割点或者树根。 当这个点是割点时，它所属的点双必定不可以向它的父亲方向覆盖更多点，因为一旦覆盖了，它就成为了新的子图的一个割点，不是点双。所以它应该归到其中一个或多个子树里的点双中。 当这...

割点(Tarjan) 题意概述 给出一个 个点， 条边的无向图，求图的割点。 思路 ：是第几个被访问到的 : 点通过一条返祖边能回到的$dfn值最小的点是哪一个 对于点, 它的所有儿子中不存在能通过返祖边或者横插边越过它的，那么这个点就是一个割点 也就是, 是父亲，是儿子，一旦有,那么就是一个割点 代码 #include <bits/stdc++.h> const int maxn = 2e4 + 10, inf = 2e5 + 10; bool ifcut[maxn] = {0}; int cnt = 0, n = 0, m = 0, u = 0, v = 0, s= 0...

画圈游戏（匈牙利算法） 题意概述 有一个的方格图，有一些格子上面有星星，可以画圈，每个圈最多覆盖相邻两个格子，要覆盖每一个星星至少画几个圈 思路 最好的情况：一个圈包含了两个星星---最大匹配 然后就剩下了单个的孤寡星星，只能用单个圈覆盖 假设有个最大匹配，一共个星星，一共需要个圈 最小边覆盖 顶点数 最大匹配 代码 #include <bits/stdc++.h> inline int read() { int x = 0, flag = 1; char ch = getchar(); while(ch < '0' || ch > '...

强连通分量（Tarjan） 个人认为：求强连通分量的过程就是缩点的过程 算法主要步骤 时间戳 点和它子树中的返祖边和横插边能连到还没有出栈的的最小的点 在的时候维护一个栈，第一次访问某一个节点时就把这个点加入到栈中，当一个点的时，它就是这个强连通分量在搜索树中最高的点，将栈里的点出栈，知道点也出栈，这些点构成一个强连通分量 一些思考 当时，它就不能通过返祖边或者横插边去到比它更靠上的点了 理解它的正确性: 在dfs中，先出栈的点一定能被后出栈的点到达 越是靠后出栈就越有可能到达不了 （） 所以当访问到了一个的点时，一定是通过横插边或者返祖边回到了之前某个点，也就组成了一个强连通分量 ...

树形DP的经典------二叉苹果树 题意概述 一棵苹果树，有边权，保留一定数量的边，问边权之和最大多少 思路 为什么和01背包有关----每一个分叉都有选和不选的两种可能 表示以i为根的子树选择了j条边能达到的最大权值 子树到底选不选 如果不选的话 如果选的话 注意这里是的原因是，选择了子树后又会向连一条边 那么 这样其实就是一个树上01背包问题了 这个题还需要存每一棵子树的边数 代码 #include <bits/stdc++.h> #define endl '\n' // #define int long long using lli = long long; us...

没有上司的舞会 题意概述 每一个点都有一个权值 对于一个点i，如果选了它，那么它的儿子就不能选了。如果不选它，那么它的儿子可选可不选 问怎么选，使得总权值和最大 思路 对于一个点，如果它的父亲选了，那么它一定选不了 如果它的父亲没有选，它就可以选也可以不选 那到底选还是不选---选一个最有利的情况 那么每个点就有两种状态了：选或不选 用标识不选，标识选 不选i点时，i点及其子树能选出来的最大价值 选i点时，i点及其子树能选出来的最大价值 那么最终结果就是 状态转移：对于点不选，那么它的儿子可选可不选， 对于点选了，那么它的儿子就不能选了， 边界情况：对于叶子节点 代码 // 没有上...

多重背包 每一个物品数量是确定的 思路 如果每个物品数量一件，那么就还是一个01背包问题 可以把假设可以把第i件物品数量为num[i]，可以看成num[i]个相同的物品，这样还是一个01背包问题，但是时间和空间都接受不了 二进制优化 一个数总能写成二进制序列，可以分解成 把一个多个数量的物品分成这样几份，可以想要几个都可以实现，但是时间和空间变成了 看以看一下这个 // val[i] 物品i的价值 // weight[i] 物品i的重量 // a 单个物品的价值 // b 单个物品的重量 int k = 1; cnt = 0; while(k <= s)//k为枚举个数，s为物品总件...

(模板)KM算法——带权二分图的最大匹配 升级版匈牙利算法 题意概述 有n个人，n个房子，每个人到房子都有一定的距离，问怎么匹配总距离最小 思路 可以看成是一个二分图，人在左集合，房子在右集合 这就是一个带权二分图的最优匹配问题 但是让求的是最小匹配怎么办呢，可以把权值存成负数，输出的时候再加一个负号就好了 算法主要步骤 为左右集合设置顶标，左集合顶标为所连线权值最大值，左集合顶标为0, 设 如果 ,则 为左集合匹配，匹配成功更好，匹配失败的话，遍历左集合已经匹配的点，让他们降低标准，让代价最小，为。然后遍历右集合未匹配的点，符合要求就做匹配 再次匹配后，遍历本轮匹配过程中遍历过的点，左...