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-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-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
继续阅读