题意：给你2个数组，让你求一个最大的p使得任意的（l，r）属于 1<=l<=r<=p   使得RMQ（a,l,r）==RMQ(b,l,r)； 从第一个数开始往后找，比他大的数没有影响，只要碰见比栈顶元素小的数，就一直pop，直到遇见比他小的栈顶 #include<bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N],b[N]; int ta,tb; stack<int> qa,qb; int main(){ int n; while(~scan...

链接：https://ac.nowcoder.com/acm/contest/881/B 来源：牛客网   Bobo knows that  Given n distinct positive integers a1,a2,…,anfind the value of It can be proved that the value is a rational number Print the result as  输入描述: The input consists of several test cases and is terminated by end-of-file. The fi...

  题意：有n个巫妖，m个精灵，k棵树，他们都有自己的位置坐标表示。巫妖有冷却时间和范围。树有覆盖范围。 假设某个巫妖攻击精灵的路线（他俩之间的连线）经过树的覆盖范围，表示精灵被树挡住巫妖攻击不到。求巫妖杀死所有精灵的最少的时间。若无法所有杀死输出-1；   巫妖能否打到精灵用线段与圆是否相交来推断，若相交，就攻击不到。 由于时间越长攻击的精灵越多，所以时间可以用二分解决。 二分出一个时间，然后建图，用最大流跑，结果如果等于m则时间可以再小。 直到结果不等于m 建图的时候源点连接 精灵，精灵连接巫妖，巫妖连接汇点， 这样的好处是，精灵可以被女巫杀死，而女巫的杀伤力由二分的时间...

题目链接：http://codeforces.com/contest/546/problem/E 题意：给你n个城市，每个城市原来有ai个士兵，每个城市想要达到目标士兵数是bi， 士兵可以沿着某条路走  或者 在原来的城市不动，只能走一次。给你m条路，问能不能使得所有的城市满足目标 难点在于建图上。  由于士兵可以选择不移动，那么需要把城市拆点，一个当做起始点，一个当做目标点 m条边连接 的时候由于是无向边，所以需要addedge 两次 像下图 一个起点可以对应本身的终点（如果这条边有流量，相当于一些士兵 不移动，），也可以指向其他的终点（如果有流量，则代表有一些士兵走向了其他点...

题目链接  ：http://poj.org/problem?id=3436 题目很难理解，读题的时候读蒙了，看了好多解释才理解，简单点就是有很多机器来生产电脑，这些机器  可以通过利用一些零件生成或者销毁一些零件，也可能通过一些零件直接生成一台电脑。 利用的零件  给出的输入形式为  0代表这台机器工作的时候不需要这种零件，1代表必须要这种零件，2代表可有可无 工作产生的结果是输出形式为  1代表生成了这种零件，0代表没有生成这种零件 所以建图的时候  需要一个超级源点，一个超级汇点，由于在点上有权值，所以需要拆点 超级源点连接的是  输入形式中没有1的 容量为INF 超级汇点连接...

题目链接：http://poj.org/problem?id=3281 题意：给你n头牛，F种吃的，D种喝的，每头牛对某些吃的喝的情有独钟，每种吃的  和  喝的  只能给一头牛，一头牛只能得到一 种吃的一种喝的，而且一头牛必须同时获得吃的和喝的 才能被满足   问最多有多少头牛可以满足  一个最大流模板题，不过建图容易出错，需要注意的是牛需要拆点就行了。 是一个二分匹配问题，不过是两个条件必须满足，所以牛 需要拆点。 #include <algorithm> #include <vector> #include <cstdio> #incl...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4280 题意：给你n个岛屿的坐标，让你求从最西边到最东边的最大流 （题目保证只有一个点在最西边，只有一个点在最东边） 这个题比较卡时间 普通 dinic（） 9375ms kuangbin模板  4992ms ISAP+bfs初始化+栈优化  3572ms   #include <algorithm> #include <vector> #include <cstdio> #include <queue> #include <c...

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4289 题意：给你n个点，m条边，一个起点，一个终点，意思是一群***从起点出发到终点作案，要求你在一些点建立检查点，用最小的花费使得***到达不了终点。 由于是每个点上有花费，所以把点拆开，设置成  当前点到新点的距离为当前点的花费 即add（i，i + n，c）; m条边为 add（u+n，v，INF）; add（v+n，u，INF）; 起点为s，终点为  t+n   其他就是最大流模板 #include <algorithm> #include <vect...

题目链接：https://cn.vjudge.net/problem/HDU-6214 题意：给你n个点，m条边，源点s，汇点t，让你求最小割的最少变数 思路和我上一篇博客HDU-3987一样 两个思路： 1、先跑一遍最大流，然后让饱和的边的容量置为1，不饱和的置为INF，再跑一遍最大流即可 2、让每条边的边权乘上一个大于边数的数再加1，然后跑一边最大流，最后输出结果%乘的那个数即可   #include <algorithm> #include <vector> #include <cstdio> #include <queue&gt...

题目链接：https://cn.vjudge.net/problem/HDU-3987 题意：给你n个点，m条边（有单向边也有双向边），由于最小割不止一种，求所有最小割种，边数最少的那个割集，输出最少的边数 两个思路： 1、先跑一遍最大流，然后让饱和的边的容量置为1，不饱和的置为INF，再跑一遍最大流即可 2、让每条边的边权乘上一个大于边数的数再加1，然后跑一边最大流，最后输出结果%乘的那个数即可 #include <algorithm> #include <vector> #include <cstdio> #include <queue...

题目链接：https://cn.vjudge.net/problem/HDU-3605 题意：给你n个人，m个星球，每个人对这m个星球的都有一定的适应能力，每个星球都有一定的容纳量，问能否让所有的人在星球上生存。 刚开始做的时候一直TLE 不知道为什么，改着改着发现建图的时候，添了很多边，这样跑最大流非常慢，看了网上的思路才知道要缩点，因为星球最多才有10个，所以把每个星球适合住的人数存一下，当做源点与星球的边的流量，星球的最大容纳量当做星球与汇点的边的流量。 跑一遍dinic，最大流大于等于n即YES 否则NO #include <algorithm> #includ...

本文转自：https://www.cnblogs.com/linzhengmin/p/9313216.html   Dinic算法本身，自然是解决最大流(普通最大流，最大流最小割)的算法。通过处理，也可以解决二分图的最大匹配（下文介绍），最大权闭合图。 算法介绍：介绍Dinic之前，我们先介绍一下最大流。在最大流的题目中，图被称为"网络"，每条边的边权被称作"流量"，有一个起点（源点）和一个终点（汇点）。我们要求的最大流，可以这样形象地理解：源点有一个水库，里面有无限吨水（QWQ），汇点也有一个水  库，希望得到最多的水。我们假设每个河道一天只能输...

题目链接：https://cn.vjudge.net/problem/HDU-1533 题意:给你n个房子n个人  使得所有人都有一座房子的最小花费 思路：把所有的人与房子建边，最后，源点与所有的人建边，所有的房子与汇点，跑一边最消费用最大流即可   #include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <cstring> #include <queue> #define ll long long #de...

题目链接：https://cn.vjudge.net/problem/CodeForces-555B 题目大意：n个岛屿，在一条线上，岛屿有起点和终点，有m座桥，问能不能用n-1座桥把岛屿连起来 思路：可以先把n个岛屿的位置  预处理成n-1个所需桥的长度范围，然后按照左端点升序排列，把桥的长度按照升序排列 对于每个桥筛选出满足条件的岛屿区间  因为对于区间已经升序了，所以选择一个较小的右端点，可以保证其他的区间有更多的选择 #include <bits/stdc++.h> #define ll long long using namespace std; const i...