题目描述 GG 公司有 nn 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 nn 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。 输入格式 文件的第 11 行中有 11 个正整数 nn，表示有 nn 个仓库。 第 22 行中有 nn 个正整数，表示 nn 个仓库的库存量。 输出格式 输出最少搬运量。 输入 5 17 9 14 16 4 输出 11 这道题很容易看出是一道最小费用最大流问题， 当然也可以用数学加贪心的方法过题， #include<cstring> #include<algorithm>...

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<queue> #include<vector> using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 1e5 + 5; struct Edge { int to, next; long long w; }edg[MAXN]; int head[MAXN], dep[...

今天讲的建图方法主要用来解决同时做问题，和第一期讲的拆点法有点相似，但是实际上却有很大差距，第一期的酒店之王拆点法，就要原因是为了解决一个点可能会被多次匹配的问题，也就是说主要作用是限流的作用，而这次的拆点主要是解决同时做的问题，也就是把一个点拆成n个，使之具有n种状态，还是会重题目说起洛谷2053 题目描述 同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。 输入格式 ...

这期讲的是网络流建图方法五—— 一对多问题，这类题呢，通常是一个决策影响多个决策比如洛谷P3980这道题， 题目描述 申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案...

网络流建模方法（四）互不攻击问题，或者说是共存问题， 这类题目看起来有点像二分图匹配，这类题目我们就是建一个二分图然后跑最大流 还是先说题目洛谷P3353 题目描述 在一个 nn个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入 对于给定的 nn 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击 输入格式 第一行有 2 个正整数n 和 m (1<=n<=200, 0<=m<n2)，分别表示棋盘的大小和障碍数。接下来的 m 行给出障碍的位置。每行 2 个正整数，表示障碍的方格坐标。 输...

网络流建模方法三描述每一个决策的问题， 其实网络流一直都在做这个事，去描述决策的问题， 把他称之为一种建模方法似乎有一点过分，或者应该将其称之为一种题型，一种描述决策的题型吧！还是先说题目 洛谷P1251 题目描述 一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 ii 天需要 r_ir i块餐巾( i=1,2,…,N)。餐厅可以购买新的餐巾,每块餐巾的费用为 pp 分;或者把旧餐巾送到快洗部,洗一块需 m 天,其费用为 f 分;或者送到慢洗部,洗一块需 nn 天(n>mn>m),其费用为 ss 分(s<fs<f)。每天结束时,餐厅必须决定将多少块脏的餐巾...

inic声明:本博客默认读者会最大流最小割的定理，会Dinic, 最小割在数值上 == 最大流 <mark>但是在意义上没有任何关系，姑且可以这样求得最小割，当然可以自行百度最小割的证明定理</mark> 还是从题目开始说起 洛谷P1361 <mark>题目描述</mark> 小M在MC里开辟了两块巨大的耕地A和B（你可以认为容量是无穷），现在，小P有n中作物的种子，每种作物的种子有1个（就是可以种一棵作物）（用1…n编号）。 现在，第i种作物种植在A中种植可以获得ai的收益，在B中种植可以获得bi的收益，而且，现在还有这么一种神奇的现象，就...

众所周知图论中网络流问题最重要的就是建图了，如果可以建图成功了那么题目也就自然而然的做出来了，今天介绍的是拆点法建图，首先来看例题洛谷P1402 <mark>题目描述</mark> XX酒店的老板想成为酒店之王，本着这种希望，第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等，也有自己所爱的菜，但是该酒店只有p间房间，一天只有固定的q道不同的菜。 有一天来了n个客人，每个客人说出了自己喜欢哪些房间，喜欢哪道菜。但是很不幸，可能做不到让所有顾客满意（满意的条件是住进喜欢的房间，吃到喜欢的菜）。 这里要怎么分配，能使最多顾客满意呢？ <m...

Given a set of n DNA samples, where each sample is a string containing characters from {A, C, G, T}, we are trying to find a subset of samples in the set, where the length of the longest common prefix multiplied by the number of samples in that subset is maximum. To be specific, let the samples be:...

A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary. You are to find all the hat’s words in a dictionary. <mark>Input</mark> Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will...

匈牙利算法 <mark>什么是匈牙利算法</mark> 匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。 以上均是书上语言，简单来说匈牙利算法就是用来求解二分图匹配问题 的； <mark>思路</mark> 接下来我们来说一下匈牙利算法的思路，匈牙利算法主要是通过，不断地寻找增广路（增广路径的定义：设M为二分图G已匹...

=<mark><mark><mark><mark><mark><mark><mark><mark><mark><mark><mark><mark><mark><mark>以下是最小生成树+并查集</mark></mark></mark></mark></mark></mark></mark></mark></mark>&l...

<mark>Problem Description</mark> 虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中 会遇见很多人（白马王子，0），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经...