icontofig | 发布于 2019-07-23 13:56:02 | 阅读量 430 | 最短路 网络流 最小割
发布于 2019-07-23 13:56:02 | 最短路 网络流 最小割
2019 Multi-University Training Contest 1 1005 Path 最小割+最短路
题目大意给出一张图,让你删除一些边,使得从1到n的最短路变大,代价为删除边的长度。若本身1与n不连通则输出0。 题解有人说dinic 会T炸,那应该是他们dinic板子不够优。 这题其实就是先求出1——n的所有最短路,以所有最短路为边建一张图,然后割掉一些边使得1与n不连通。 这是很明显的最小割模型……我们最小割的原图中的所有边的流量即为其原先的长度。 至于如何求所有最短路。 直接求出从1出发的单源最短路,然后遍历一遍所有边,检查当前的边是否是最短路上的边即可。 我寻思我用复杂度比较玄学的SPFA+dinic也过去了啊……而且是1A那种,怎么那么多人说会T炸呢? 代码#include <
继续阅读
icontofig | 发布于 2019-07-15 17:15:53 | 阅读量 261 | 网络流
发布于 2019-07-15 17:15:53 | 网络流
骑士共存问题 [网络流24题] 二分图最大独立集
题解很明显能看出来同色的格子之间是不会相互攻击的。 于是我们就可以把这张图分成一张二分图了,然后建边跑最大流。 有攻击关系的点需要连一条流量为1的边。 不过值得注意的是,要优化建边方法,不然会超时。 既然是二分图,我们考虑黄色格子代表的点与S连边,红色格子代表的点与T连边,在考虑攻击关系的时候,只从黄色格子连向红色格子就可以了(因为互相攻击,所以是等价的,当然与上述方案完全反过来建边也可以)。 我们要求的是最多的共存骑士,所以是明显的二分图最大独立集的问题,求出的最大流相当于一个最小割,用总数n*n-m再减去这个最小割就是最大独立集的最后剩余的数目。 代码#include <bits/s
继续阅读
icontofig | 发布于 2019-07-13 19:09:19 | 阅读量 297 | 最短路 二分 离散化 网络流 最大流
发布于 2019-07-13 19:09:19 | 最短路 二分 离散化 网络流 最大流
BAPC18 I In Case of an Invasion,Please... 最短路+离散化+二分+最大流
题目大意有n个居民点,m条双向有权路径,和s个避难所。每个居民点有pi个居民,每个避难所的容量为Ci。 现在求能够让所有人避难的最少的需要的时间。 题解我们如果有一个时间,那么我们该如何判断在这个时间内能不能安置所有居民呢? 很简单就能想到,这是一个利用最大流判断是否存在可行流的问题。 建立从源点s到每个居民点的容量为pi的有向边,从每个居民点到每个避难所容量为+∞的有向边,从每个避难所到汇点t容量为ci的有向边。然后建完图直接跑最大流,判断最大流的流量是否等于所有的居民人数总和即可。 那这个时间我们该如何去求? 答案是可以二分。 二分出一个答案时间,然后检验这个时间下能否将所有人安置好。当然
继续阅读
icontofig | 发布于 2019-07-07 11:01:45 | 阅读量 354 | 网络流 最大流
发布于 2019-07-07 11:01:45 | 网络流 最大流
题目描述给定正整数序列x1,...,xn 。 (1)计算其最长不下降子序列的长度s。 (2)计算从给定的序列中最多可取出多少个长度为s的不下降子序列。 (3)如果允许在取出的序列中多次使用x1和xn,则从给定序列中最多可取出多少个长度为s的不下降子序列。 编程任务: 设计有效算法完成(1)(2)(3)提出的计算任务。 输入输出格式输入格式:第1 行有1个正整数n,表示给定序列的长度。接下来的1 行有n(n ≤ 500)个正整数n:x1, ..., xn。 输出格式:第1 行是最长不下降子序列的长度s。第2行是可取出的长度为s 的不下降子序列个数。第3行是允许在取出的序列中多次使用x1和xn时可
继续阅读
icontofig | 发布于 2019-07-03 17:41:17 | 阅读量 99 | 网络流 最小割
发布于 2019-07-03 17:41:17 | 网络流 最小割
洛谷P1344 [USACO4.4]追查坏牛奶Pollutant Control 基础最小割模型
题解说实话这是一个水题……一眼看出来就是最小割模型…… 我们只需要付出最小的代价破坏汽车(可以看作是道路)使得S和T不连通就行了。 于是我们连有向边,以损失为此边流量。建好图直接跑1到N的最小割就是了。这样最小损失就求出来了。 至于第二问,我们可以像第一问一样把边的流量改为1,然后再跑最小割。这是一定正确的,请自行证明。 代码#include <bits/stdc++.h> using namespace std; int get_num(){ int num = 0; char c; bool flag = false; while((c = getchar()) ==
继续阅读
icontofig | 发布于 2019-04-27 22:35:58 | 阅读量 440 | 最小割 网络流
发布于 2019-04-27 22:35:58 | 最小割 网络流
BZOJ 2561 最小生成树(最小割模型)
题解:我们先来考虑一下我们在使用kruskal算法的时候是怎么生成最小生成树的。 Kruskal算法是一种贪心算法,每次选择边权最小的一条边,检测一下两个端点是否都在一个并查集里,如果不是就加上这一条边,代表最小生成树选择这一条边。 于是这便是此题的关键,如果想要让新加进去的边可能出现在最小生成树中,那么在所有边权小于新边的边集中,就不能有一个子集使得新边的u和v连通。 如果有这样的边集,我们就要通过删边去破坏掉,而且使得破坏掉的边尽可能的少。 诶这不是完美契合最小割模型吗……可是这数据范围…… 放心,dinic能顶得住……网络流的复杂度从来都是玄学,这话可不是假的…… 于是对于最小生成树,我
继续阅读
icontofig | 发布于 2019-02-24 16:33:29 | 阅读量 229 | 网络流 费用流 最大流
发布于 2019-02-24 16:33:29 | 网络流 费用流 最大流
DescriptionMZL is an active girl who has her own country. Her big country has N cities numbered from 1 to N.She has controled the country for so long and she only remebered that there was a big earthquake M years ago,which made all the roads between the cities destroyed and all the city became broke
继续阅读
icontofig | 发布于 2019-02-14 10:43:38 | 阅读量 291 | 网络流 最小割 最短路
发布于 2019-02-14 10:43:38 | 网络流 最小割 最短路
DescriptionInnocent Wu follows Dumb Zhang into a ancient tomb. Innocent Wu’s at the entrance of the tomb while Dumb Zhang’s at the end of it. The tomb is made up of many chambers, the total number is N. And there are M channels connecting the chambers. Innocent Wu wants to catch up Dumb Zhang to fin
继续阅读
icontofig | 发布于 2019-02-14 09:39:19 | 阅读量 329 | 网络流 费用流
发布于 2019-02-14 09:39:19 | 网络流 费用流
BZOJ 1937 Mst最小生成树
Description Input第一行为N、M,其中 表示顶点的数目, 表示边的数目。顶点的编号为1、2、3、……、N-1、N。接下来的M行,每行三个整数Ui,Vi,Wi,表示顶点Ui与Vi之间有一条边,其权值为Wi。所有的边在输入中会且仅会出现一次。再接着N-1行,每行两个整数Xi、Yi,表示顶点Xi与Yi之间的边是T的一条边。 Output输出最小权值 Sample Input6 9 1 2 2 1 3 2 2 3 3 3 4 3 1 5 1 2 6 3 4&
继续阅读
icontofig | 发布于 2018-12-26 10:18:42 | 阅读量 189 | 网络流 tarjan 最大流
发布于 2018-12-26 10:18:42 | 网络流 tarjan 最大流
NOI2009 植物大战僵尸(最大权闭合子图、联通量处理)
题目描述 输入格式 输出格式仅包含一个整数,表示可以获得的最大能源收入。注意,你也可以选择不进行任何攻击,这样能源收入为0。 样例输入3 2 10 0 20 0 -10 0 -5 1 0 0 100 1 2 1 100 0​样例输出25​数据范围及提示在样例中, 植物P1,1可以攻击位置(0,0), P2, 0可以攻击位置(2,1)。一个方案为,首先进攻P1,1, P0,1,此时可以攻击P0,0 。共得到能源收益为(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,
继续阅读