来源：牛客网  文章目录    题目描述 题解： 代码：    时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld  题目描述  给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图， 输出一个尽可能小的点集，使得从这些点出发能够到达任意一点，如果有多个这样的集合，输出这些集合升序排序后字典序最小的。 输入描述: 第一行为两个整数 1 ≤ n, m ≤ 105， 接下来 M 行，每行两个整数 1 ≤ u, v ≤ 105 表示从点 u 至点 v 有一条有向边。 数据保证没有重...

Tarjan算法可以应用在求解 强连通分量，缩点，桥，割点，双连通分量，LCA等 关于  文章目录    强连通分量   代码 题目  tarjan求割点   割点概念 流程 代码：  求无向图的割边／桥   理解： 代码：  强连通分量缩点   大致流程： 代码： 例题  Tarjan求LCA   关于LCA本人博客讲解 例题  双连通分量   点双连通图 边双连通图      对于一个连通图，如果任意两点至少存在两条点不重复路径，则称这个图为点双连通的（简称双连通）；如果任意两点至少存在两条边不重复路径，则称该图为边双连通的。点双连通图的定义等价于任意两条边都同在一个简单环中，而边双连通图...

最大流的算法有很多，有FF算法，EK，Dinic，ISAP等   文章目录    FF算法   流程：  EK算法 Dinic算法   Dinic与Ek比较  算法主要应用     增广路就是一条从起点，到终点的一条每边容量 - 实际流量>0的路 所有最大流算法的精华部分是引入反向边 利用反向边，给程序一个返回和改正的机会 FF算法 流程： 1.在图上找到一个从源点到汇点的路径（也就是增广路） 2.取增广路上的残量最小值v（也就是流过的路径中流量最小的那一个） 3.将答案加上v 4.将增广路上所有边的残量减去v，反向边的产量加上v 5.重复1~4，直到找不到增广路 struct Edge...

Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 93263 Accepted: 36174  试题链接   文章目录    Description 题意： 题解： 代码：   Dinic做法 EK做法     Description  Every time it rains on Farmer John’s fields, a pond forms over Bessie’s favorite clover patch. This means that the clover is covered by water for a...

P2756 飞行员配对方案问题   文章目录    题目背景 题解： 代码：    题目背景  第二次世界大战期间，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的两名飞行员，其中一名是英国飞行员，另一名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。  题目描述  一共有 n 个飞行员，其中有 m 个外籍飞行员和 (n - m) 个英国飞行员，外籍飞行员从 1 到 m 编号，英国飞行员从 m + 1 到 n 编号。 对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方...

文章目录    题目描述 题解： 代码：     添加链接描述 题目描述  T 公司发现其研制的一个软件中有 n 个错误，随即为该软件发放了一批共 m 个补丁程序。每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时，往往会加入另一些错误。 换句话说，对于每一个补丁 i，都有 2 个与之相应的错误集合 B1[i]和 B2[i]，使得仅当软件包含 B1[i]中的所有错误，而不包含 B2[i]中的任何错误时，才可以使用补丁 i。补丁 i 将修复软件中的某些错误 F1[i]，而同时加入另一些错误 F2[i]。另外，每个...

大创项目是图像识别，第一个任务是将一个图片转换成二值图像  之前用过python的numpy和turtle，这次要用到图像库PIL的类Image，也算是刚刚从零开始学起 整体效果（用01串表示图像）    原理很简单：将图片中黑色部分用0，其余部分用1 详细过程： 先读取照片，获取图片的像素，然后对像素进行缩放，再对缩放后的照片黑白（如果原本是彩色图）。 然后一次获取图像中每一点像素的RGB颜色值，若为黑色则将该像素替换为0，其余为1 用一个字符串存储，最后按照指定长宽输出 用到的工具： im.getpixel((j, i)) #getpixel是获取图像中某一点像素的RGB颜色值 im = ...

均分纸牌有三种情况：线性，环形，二维   文章目录  线性   题目描述 思路： 代码：  环形     题目描述 思路 代码     线性 题目描述 P1031 均分纸牌 有N堆纸牌，编号分别为1,2,…,N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。 移动规则:只能向相邻的纸牌移动 问最少移动多少次可以使纸牌数一样多 思路： 第一堆只能给第二堆多干张，或者第二堆给第一堆，这取决于第一堆的初始牌量。当确定第一堆状态后，我们就不用再考虑他，第二堆就变成新的第一堆。 所以我们先求平均值（也就是最终每堆多少张），然后从第一堆开始往后一次比较，如果相等就跳过，如果...

文章目录    题目描述 题解： 方法一：   代码：  方法二：     P4016 负载平衡问题 题目描述  G 公司有 n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 n 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。  输入格式  第一行一个正整数 n，表示有 n 个仓库。 第二行 n 个正整数，表示 n 个仓库的库存量。  输出格式 输出最少搬运量。 输入输出样例 输入 #1复制 5 17 9 14 16 4  输出 #1复制 11  说明/提示 1≤n≤100。 题解： 和网络流啥关系。。。又是老婆饼里没老婆？ 方法一： 环形均分...

P4011 孤岛营救问题   文章目录  输入输出样例 题意： 题解：   代码：    输入输出样例 输入 4 4 9 9 1 2 1 3 2 1 2 2 2 0 2 1 2 2 0 2 1 3 1 0 2 3 3 3 0 2 4 3 4 1 3 2 3 3 0 3 3 4 3 0 4 3 4 4 0 2 2 1 2 4 2 1  输出 14  题意： (原题太长我就不贴了，简单叙述一下) 一个N*M的迷宫，每个单元格之间可能有门或者墙，也可能啥也没有。门和墙的总数为K（会读入墙和门的位置坐标） 门存在种类，只有拥有对应种类的钥匙才可以打开这类门 钥匙的总量为S（会读入钥匙的坐标） 从一个单...

P4015 运输问题   文章目录    题目描述： 输入格式： 输出格式： 输入输出样例： 题解： 代码：    题目描述：  输入格式：  输出格式： 两行分别输出最小运输费用和最大运输费用。 输入输出样例： 输入 #1 2 3 220 280 170 120 210 77 39 105 150 186 122  输出 #1 48500 69140  题解： 最小费用最大流(MCMF)问题 根据样例数据分析： 橙色为第一个仓库晕倒各零售商店的单位费用 绿色为第二个  一边是仓库，一边是商店，典型的二分图，还是完全二分图 我们可以在仓库的左边设置一个源点S，右边设置一个终点T。S指向每一个仓...

1.我才知道a=input()读入的竟然是字符串。。。还要强制转化成int型，这玩意搞了我好久 2.对照片进行裁剪，将照片周围多余的白色部分去除（也就是让图像尽可能撑满整个框）  由上一张裁成下一张  from PIL import Image import os SCALE = 1 #等比例缩放 def get_char(pixel, blank_char='0', fill_char='1'): return blank_char if pixel == 0 else fill_char def shang(): for i in range(width): for j in range(...

文章目录  求斐波那切数列的几个方法：   经典做法：   递推： 动态规划  矩阵快速幂   原理： 代码： 例题：  模拟过程    求斐波那切数列的几个方法： 经典做法： 众所周知：斐波那契数列的定义是f(n + 1) = f(n) + f(n - 1) 我们有两种方式来实现：一个是递归，一个是动态规划 递推： int dfs(int n) {  if (n == 1) return 1; if (n == 2) return 2; return dfs01(n - 1) + dfs01(n - 2); }  动态规划 int dfs03(int n) {  vec[maxn] vec[...

文章目录    普通矩阵（单个矩阵值为任何数）   最大子段和 扩展到二维情况  01矩阵（单个矩阵值为0或1） 代码：    普通矩阵（单个矩阵值为任何数） 例题：POJ 1074  求出其中最大的子矩阵 答案是： 9 2 -4 1 -1 8 最大和是15 我们先想想如果不是矩阵，是一个数组，求其中连续的最长一段，咋做？ 最大子段和 我们用b[i]来表示a[0]…a[1]的最大子段和 那么b [ i ] =max ( b [i - 1 ] + a [ i ], a [ i ] ) 当a[n] 大于dp[n-1]（前n-1个元素序列的最大子段和）。此时舍弃前面的子段和，即断开。 否则的话，把a...