141
最大流问题

定义 有m条管道,n个节点,1为水源(源点),n为终点(汇点),每条管道有水流量上限,问如何分配每条水管的流量才能使终点处接受到的水流量最大。 最小割最大流定理:是指在一个网络流中,能够从源点到达汇点的最大流量等于如果从网络中移除就能够导致网络流中断的边的集合的最小容量和。 算法&模板 EK(最短增 ...

UCPRER @ 2019/07/28

142
剑指offer第二版面试题5:从尾到头打印链表(JAVA版)

题目描述: 输入一个链表,从尾到头打印链表每个节点的值。返回新链表。 ...

沦为旧友 @ 2019/07/28

143
队列问题非STL解决方案

队列问题非STL解决方案 常年使用STL解决队列问题,以至于严重生疏队列的根本原理。。。 直到今日 ~~被老师被迫~~ 使用算法原理解决问题,方才意识到我对队列一窍不通。。。 。。。直到 ~~经过一系列的坑蒙拐骗~~ 之后,方才理清楚一些头绪,在此附记。 有关概念在此不再赘述,~~因为这东西怕不是一 ...

IZWB-003 @ 2019/07/28

144
POJ1861(Network)-Kruskal

题目在这 Sample Input Sample Output 题目意思:4个点,6个边,每个边有对应的权值。最后输出一行为路径中最大的边的值,第二行为路径上边的总数, 第三行为每条边的始末编号。题目需要求出最小生成树的最大边的最小值。 1 /* 2 Problem: 1861 User: 3 Me ...

回忆酿的甜 @ 2019/07/28

145
最小生成树-Kruskal算法

与Prim算法贪心选择不同,Kruskal算法采取每次选择权值最小的边的方法,这样,在不构成环且最后能够连接完所有边它们的权重和一定是最小的。 和之前Prim算法的图一样,便于区别二者。 Kruskal既然是选择最小的边,那么就先找一个最小的出来,是1-6(10) 然后继续找出剩下的边中最小一条边, ...

回忆酿的甜 @ 2019/07/28

146
POJ1611(The Suspects)--简单并查集

题目在这里 关于SARS病毒传染的问题。在同一个组的学生是接触很近的,后面也会有新的同学的加入。其中有一位同学感染SARS,那么该组的所有同学得了SARS。要计算出有多少位学生感染SARS了。编号为0的同学是得了SARS的。 直接用并查集解决水掉 1 #include<iostream> 2 #in ...

回忆酿的甜 @ 2019/07/28

149
算法-一步步教你如何用c语言实现堆排序(非递归)

看了左神的堆排序,觉得思路很清晰,比常见的递归的堆排序要更容易理解,所以自己整理了一下笔记,带大家一步步实现堆排序算法 首先介绍什么是大根堆:每一个子树的最大值都是子树的头结点,即根结点是所有结点的最大值 堆排序是基于数组和二叉树思想实现的(二叉树是脑补结构,实际是数组) 堆排序过程 1、数组建成大 ...

陈佳乐 @ 2019/07/27

151
Tarjan无向图的割点和桥(割边)详解&算法笔记&通俗易懂

"原文链接" Tarjan无向图的割点和桥(割边) 导言 在掌握这个算法前,咱们有几个先决条件. [x] DFS搜索 [x] DFS序 [x] 一张纸 [x] 一支笔 [x] 认真的大脑~~(滑稽)~~ 如果您都具备了,那么您就是巨佬了,您就可以轻松解决Tarjan算法了. 初学算法 概念掌握 割点 ...

秦淮岸灯火阑珊 @ 2019/07/27

152
CodeForces - 1159B

SSummerZzz @ 2019/07/27

153
LeetCode.1103-向人们分发糖果(Distribute Candies to People)

这是小川的第 393 次更新,第 425 篇原创 01 看题和准备 今天介绍的是 LeetCode 算法题中 Easy 级别的第 256 题(顺位题号是 1103 )。我们通过以下方式向一排 个人分发一些糖果: 给第一个人送1个糖果,给第二个人送2个糖果,依此类推,直到我们给最后一个人送糖果。然后, ...

程序员小川 @ 2019/07/27

154
Marriage Match II 【HDU - 3081】【并查集+二分答案+最大流】

题目链接 一开始是想不断的把边插进去,然后再去考虑我们每次都加进去边权为1的边,直到跑到第几次就没法继续跑下去的这样的思路,果不其然的T了。 然后,就是想办法咯,就想到了二分答案。 首先,我们一开始处理关系,(一开始看错了男女关系,结局懵逼了好久),注意输入是女选男。然后,就是去处理咯,我们先要去考 ...

唔哩Wulili @ 2019/07/27

155
使用广度优先搜索,计算路径最短问题

问题,求出任意两个站点间的最短距离 广度优先搜索可解决的问题 1. 从A节点能否到达B节点 2. 从A节点到达B节点的最短路径 广度优先搜索的原理 先搜索A节点的所有子节点,过没有找到结果,再从每个子节点的字节点搜索。如此反复。 注意:必须按顺序从所有一级节点开始搜索,再从二级节点,三级节点,以此类 ...

tianzhen45 @ 2019/07/27

157
2019牛客暑期多校训练营(第三场)H Magic Line

原题链接:H Magic Line 题意简述: 给定n个点,要求画一条直线将n个点分成均有n / 2个点的两部分,不能有点在线上; 解题思路: 首先,先将所有的点进行以x为第一关键字,y为第二关键字进行排序,接着: 第一种情况 对于第二种情况,我们首先根据a1(a[n / 2].x - 1,a[n ...

zoom1109 @ 2019/07/27

158
POJ 2796 Feel Good

原题链接:POJ 2796 Feel Good 题意简述: 求某段区间的最小值*这段区间所有元素之和的最大值; 代码如下: #include<iostream> #include<cstdio> using namespace std; const int N = 100010; typedef l ...

zoom1109 @ 2019/07/27

159
Codeforces C. Split a Number(贪心大数运算)

题目描述: time limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputDima worked all day and wrote down on a lo ...

小张人 @ 2019/07/27

160
C. Roads in Berland

小鑫666 @ 2019/07/27