一颗牙疼_

未归档

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

/ 注册

全部文章 / 未归档（共20篇）

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

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

2019-08-12

0 335

网络流建模方法（三）——网络中描述每一个决策洛谷 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 361

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

二分图匹配——匈牙利算法

匈牙利算法 <mark>什么是匈牙利算法</mark> 匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。美国数学家哈罗德·库恩于1955年提出该算法。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes...

2019-05-08

0 538

图论选手刷题路线图论500题

=<mark><mark><mark><mark><mark><mark><mark><mark><mark><mark><mark><mark><m...

2019-04-24

0 437

HDU 2112 简单最短路

<mark>Problem Description</mark> 经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居了二线，并在风景秀美的诸暨市浬浦镇陶姚...

2019-04-12

0 514

HDU 2544——最短路

<mark>Problem Description</mark> 在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？...

2019-04-12

0 288