定义给一个有向图 $G=(V,E)$。对于边 $(u,v)$ 有容量 $w(u,v)$。可以理解为为水管在单位时间可以流过的最大水量。现在给定源点 $s$，和汇点 $t$，可以将源点理解为单位时间内可以留任意的水量的水龙头，汇点可以理解为可以装无限水的容器，最大流指源点发出的“水”经过“水管”单位时间可以流到汇点的最大水量。FF思想对于求网络最大流问题，我们有一个基础的想法：从源点dfs，如果dfs到了汇点就将这条路径上“流水”，而流的水量就是当前我们dfs到的源点到汇点的路径中边容量的最小值，然后将所有dfs到的边都流去这个水量，相当于将这些边的容量都减少这个水量，在之后的dfs中不走已经满了（没有容量）的边。但是我们需要改进这个算法，我们发现dfs的一条路径显然不一定是最优的，所以我们让这个算法可以后悔。如何后悔，我们对于每一条边建一条容量为0反向边，每当一条边溜了 $x$ 的流量时就将反向边的容量扩大 $x$ 也就是给自己 $x$ 的反悔空间，那么现在我们就可以写出一个基础代码了，这个基础代码就是FF算法。tip:对于求一条边的反向边我们可以利用链式前向星存图方式的边的编号，让编
前言我们知道线段树可以处理区间修改/查询操作，那么如果这个区间修改/查询变成了树上任意一条路径上点的修改/查询呢？比如我们需要满足一下几个操作 ：给 $u$ 到 $v$ 路径上的每一点都加上 $k$查询 $u$ 到 $v$ 路径上每一点的和。如果数据大的话，暴力算法是不能胜任的。树剖我们考虑将树上问题转化为区间问题，然后用线段树处理。但是一条 $u$ 到 $v$ 路径上每一点在线段树的位置不一定是连续的，所以我们可能要进行多次区间操作，因此最坏情况下甚至不如朴素算法。所以我们尽量让多的点的编号连续。概念现在我们引入几个概念和定义：时间戳 $dfn_x$：dfs时到达这个点的时间成为这个点的时间戳；重儿子 $son_x$：所有儿子中子树最大的儿子；重边：由 $x$ 到 $x$ 的重儿子的一条边；轻边：由 $x$ 到 $x$ 的非重儿子的边；重链：若干条连续的重边合称为连续的重链；$top_x$：$x$ 所在重链的顶端（当 $x$ 不在重链上时可以理解为自己到自己的重链 $top_x=x$）；f_x：$x$ 的父亲；dep_x：$x$ 的深度。核心思想对于以上的东西，我们可以通过两编 $d
1.概念强连通分量：在有向图或无向图中的点集，保证集合中每两个点都可以互相到达。割点：一个点是割点当且仅当删除这个点之后连通块的数量会增加。桥：一条边是桥当且仅当删除这条边后连同快的个数会增加。树边：遍历一个图时的dfs树上的边。非树边：图中除了树边以外的其他边。dfn：时间戳，即dfs一个图时点是第几个被遍历到的。low：子树内所有节点所能通过走非树边到的点的dfn的最小值。2.算法tarjan的算法本质其实就是在dfs图的时候求dfn和low这两个值，通过这两个值可以求出很多东西，详见应用。对于dfn很好处理，在dfs时直接记录即可。对于 $low_x$，以及现在有一条 $(x,y)$ 的边，如果 $y$ 还没有遍历过，说明这是树边，$y$ 是 $x$ 子树内的节点，所以 $low_x=\min\{low_x,low_y\}$。如果 $y$ 已经遍历过了，则这条边为非树边（此时 $y$ 有可能为 $x$ 的父亲，因为可能有重边）或者树边（此时 $y$ 必定 $x$ 的父亲）。如果是非树边的话 $low_x=\min\{low_x,dfn_y\}$。3.应用3-1割点如果一个点是割点
看题面翻译，十分清楚。传送门1.分析首先我们看到这两个交换的操作，分别定义为操作1和操作2。我们观察可以发现无论进行什么操作，原来同一列的元素操作完之后还是同一列，也就是说，对行的操作不会影响列的操作的进行，同理对列的操作不会影响行的操作的进行。转眼一看数据范围：$n \le 50$ 基本可以确定是乱搞了。2.思路得到以上的结论后，我们可以将行与列分开考虑，即只操作行的答案乘上只操作列的答案就是最终的答案。如何求只操作行（列）的答案呢？我们可以暴力 $O(n^2)$ 枚举任意2行，然后暴力判断它能否互相交换。现在我们可以发现一个事情：如果第A行和B行可以互相交换，B行和C行可以互相交换，则A行和C行显然也可以间接互相交换。于是我们设若干个行构成的集合（满足集合中每个行都可以互相直接或间接交换）为一个块。那么一个块中的行由于都可以互相交换，所以共有“数量的阶乘的阶乘”种排列方式。最后将所有块的排列方式乘起来就是只操作行的答案，我们。用同样的方式我们可以求出只操作列的答案。3.代码（有注释）#include <iostream> #include <cstring>
思路我们设奇数次操作为操作1，偶数次操作为操作2，形如 AAAAAAAA...ARCCCCCCC...C 的部分为块（ARC也是块）。很明显，任何两个块都无法融合（因为一个块中，A不能出现在右边，C不能出现在左边）。容易发现对于一个块，操作1做完之后，如果左边有A，右边有C则可以继续操作，而操作2操作完之后不能再进行操作，相当于废掉了这个块。由于每次操作2都会废掉一个块，我们需要考虑废掉那个块。很明显，废掉 “潜力” 最小的块是最优的，同样，操作1操作“潜力”最大的方块是最优的。何为“潜力”，“潜力”就是该块所能进行操作的最多次数（操作1的最多次数），也就是一直对一个块做操作1，能做多少次操作。由于每次操作1都会消耗一个块里的一个A和一个C所以一个块最多能做 $ \min \{$ 块中A的数量 $,$ 块中C的数量 $\}$ 次操作，我们设第 $i$ 个块最多能做 $x_i$ 次操作，那么我们对于每次操作的最优方案为:操作1操作 $\max_{i=1}^{n}{x_i}$操作2操作 $\min_{i=1}^{n}{x_i}$最后附上代码#include<bits/stdc++.h
题目意思给你一个 $n$ 个点，$m$ 条边的有向图，每一个边有一个权值。现在你可以修改任意条边的方向，使得原图变为有向无环图。求修改的边的最大值最小时的方案。思路看到最大值最小便很容易想到二分答案（即修改的边中的最大值），我们将这个二分的数设为 $mid$。那么很明显，图中的边会被分为两大类：权值大于 $mid$ 的边。权值小于等于 $mid$ 的边。需要解决的问题：prob1:对于第一类边我们显然是无法修改方向的，如果存在一个环且换上全是一类边。则这个 $mid$ 显然无法让原图变成有向无环图。prob2:对于第二类边我们可以改变其方向，直接统计有哪些需要改变方向的边即可。于是我们十分欣喜的发现，这两个问题都可以用拓扑排序来解决。对于prob1，我们可以将原图的二类边去掉，然后跑拓扑排序判环。对于prob2，我们在prob1的拓扑排序中顺便记录拓扑序，如果出现一个二类边是由拓扑序在后面的点指向拓扑序在前面的点，就说明这条边构成了环，将这条边记录下来即可。AT LAST 上代码#include<bits/stdc++.h> using namespace std; con
题意现在我们有 $k$ 种字符，第 $i$ 种字符有 $a_i$ 个，现在我们要将这 $\sum^n_{i=1}a_i$ 个字符按照某种顺序排列，使其符合以下形式，就称它是合法的：1个相同的-1个相同的-2个相同的-3个相同的-5个相同的-8个相同的 $...$很显然这是个菲波那切数列($1-1-2-3-5-8- ...$ )例如： $abaabbbcccccaaaaaaaa$ 就是合法的，但是 $ aabbcccddddd $ 就是不合法的。现在给出你每种字符的数量，让你判断是否可以组成合法的串。思路很容易看出一个串合法的话，它所有字符的数量肯定是斐波那契数列的前缀和 (1,2,4,7,12)，如果它所有字符的数量都不符合的话，这个串显然是不合法的。既然一个串的字符数量已经合法了的话，我们就开始考虑如何去分配了。先看样例的这一组:2 7 5我们可以判断它的数量是合法的，接下来我们把 5 它和斐波那契数列对照起来看:7 5 1 1 2 3 5这时候我们有两种选择：先用数量少的字符去放小的空先用数量多的字符去放大的空如果我们选择第一种的话:数量为 5 的字符会放满 1,1,2 后留下
题意FJ 有 $n$ 个木桩，在这 $n$ 个木桩中任意选出三个，如果这三个组成的三角形是直角三角形且两个直角边分别平行 $x$，$y$ 轴的话就将答案加上这个三角形的面积的两倍。思路1.遇事不决先暴力(得分:30pts)$O(n^3)$ 的暴力很好写，只需要枚举这三个木桩，在判断组成的三角形是否符合要求，统计答案即可。2.一个看似没用的优化(得分：还是30pts)我们可以将所有的坐标都加一个 10001 使其全部变为正数，我们在设两个vector 数组 $hx_{maxx}$ 和 $hy_{maxx}$，$hx_{X,j}$ 表示第 $j$ 个 x 坐标为X的木桩的编号。记录了这个数组后，我们就可以不用遍历那些不符合条件的木桩编号了。我们先枚举 x 坐标，然后再从所有x坐标为我们枚举到的值的木桩中找出任意两个，再枚举所有 y 坐标等于找到的第二个木桩的 y 坐标的木桩，最后统计答案即可。3.非常重要的一步(得分：50pts)我们发现上面的算法中，相当于枚举了 x 坐标相同的每个点。我们假设所有的x坐标相同的任意两个点组成的边的长度分别为:$lenx_1,lenx_2,lenx_3 .
ybaggio
