一颗牙疼_

分类

动态规划(1) 图论(5) 搜索(2) 未归档(20) 比赛(2) 贪心(1) 随笔(1)

/ 注册

全部文章（共32篇）

负载平衡问题洛谷P4016

题目描述 GG 公司有 nn 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 nn 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。输入格式文件的第 11 行中有 11 个正整数 nn，表示有 nn 个仓库。第 22 行中有 nn 个正整数，...

洛谷网络流24题最小费用最大流

2019-08-12

0 451

洛谷 P2756 飞行员配对问题，最大流配对方案输出

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<queue> #include<vector> using nam...

2019-08-12

0 333

网络流建图方法（六）解决同时做问题洛谷P2053 修车问题

今天讲的建图方法主要用来解决同时做问题，和第一期讲的拆点法有点相似，但是实际上却有很大差距，第一期的酒店之王拆点法，就要原因是为了解决一个点可能会被多次匹配的问题，也就是说主要作用是限流的作用，而这次的拆点主要是解决同时做的问题，也就是把一个点拆成n个，使之具有n种状态，还是会重题目说起洛谷2053...

网络流最小费用最大流洛谷

2019-08-11

0 322

网络流建图方法（五）—— 一对多问题洛谷 P3980 志愿者招募（最小费用最大流）

这期讲的是网络流建图方法五—— 一对多问题，这类题呢，通常是一个决策影响多个决策比如洛谷P3980这道题，题目描述申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其...

洛谷图论网络流建图最小费用最大流

2019-08-08

0 343

网络流建模方法（四）—— 互不攻击问题洛谷 P3353 骑士共存问题（附洛谷 P2774 方格取数问题）

网络流建模方法（四）互不攻击问题，或者说是共存问题，这类题目看起来有点像二分图匹配，这类题目我们就是建一个二分图然后跑最大流还是先说题目洛谷P3353 题目描述在一个 nn个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。棋盘上某些方格设置了障碍，骑士不得进入对于给定的 nn 个...

网络流建图洛谷网络流二十四题

2019-08-08

0 466

网络流建模方法（三）——网络中描述每一个决策洛谷 P1251 最小费用最大流

网络流建模方法三描述每一个决策的问题，其实网络流一直都在做这个事，去描述决策的问题，把他称之为一种建模方法似乎有一点过分，或者应该将其称之为一种题型，一种描述决策的题型吧！还是先说题目洛谷P1251 题目描述一个餐厅在相继的 NN 天里,每天需用的餐巾数不尽相同。假设第 ii 天需要 r_i...

2019-08-04

0 314

网络流建图方法（二）——辅助点（虚点）决策法洛谷 P1361 小M 的作物 Dinic

inic声明:本博客默认读者会最大流最小割的定理，会Dinic, 最小割在数值上 == 最大流 <mark>但是在意义上没有任何关系，姑且可以这样求得最小割，当然可以自行百度最小割的证明定理</mark> 还是从题目开始说起洛谷P1361 <mark>题目描述...

2019-08-01

0 531

网络流建图方法（一）拆点法 + 例题洛谷 P1402 酒店之王

众所周知图论中网络流问题最重要的就是建图了，如果可以建图成功了那么题目也就自然而然的做出来了，今天介绍的是拆点法建图，首先来看例题洛谷P1402 <mark>题目描述</mark> XX酒店的老板想成为酒店之王，本着这种希望，第一步要将酒店变得人性化。由于很多来住店的旅客有自...

2019-07-31

0 380

LOJ 1224 DNA Prefix 字典树（无需删除操作版）

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 ...

2019-07-25

0 360

HDU 1247 Hat's Word 字典树暴力

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 i...

2019-07-25

0 637