寒江陪烟火🔥

分类

acm相关(6) dp(68) RMQ(5) STL(6) 主席树(2) 二分匹配(23) 二分查找(2) 分治法(3) 划分树(1) 单调队列(2) 博弈(11) 字典树(3) 字符串处理(1) 学习(1) 并查集(4) 强联通分量(3) 归并排序(1) 拓扑排序(1) 搜索(1) 数论(8) 最小生成树(3) 最短路(5) 树状数组(7) 树链剖分(4) 欧拉回路(5) 简单模版(14) 简单题(24) 线段树(13) 网络流(6)

/ 注册

全部文章（共233篇）

并查集模版

int pre[N]; int fnd(int x) { int r=x; while(pre[r]!=r) r=pre[r]; int i=x,j; while(i!=r) { j=pre[i]; pr...

2015-09-05

0 295

HDU1937 Finding Seats（dp求最小矩形）

题目描述：告诉你人数，求最小能容纳它们的矩形的面积 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath...

2015-09-05

0 267

HDU1533 Going Home（最小费用最大流 spfa模版）

题意：给你一个N行M列的矩阵，其中“.”代表空地，“H”代表房子，“m”代表人，其中有n个房子和n个人。现在要求每个人进入一间房子，且人走一步需要支付1美元。求最小需要花费多少美元才能让所有人都进入到房子中（每个人只能进入一间房子，每个房子只能容纳一个人）。建图思路与安排工作那道题一样，...

2015-08-29

0 350

HDU3572 Task Schedule（ISAP）

学了几天的网络流，感觉还是ISAP算法比较实用，用这道题整理了一下，可以当作模版题意：给出n个任务+m台机器，还有一个任务处理时限+开始时间+结束时间，一个时刻里一台机器只能处理一个任务，但是一个任务可以在不同机器处理，问能否处理完所有任务？方法：最大流。这个题的建图算是经典，因为限定每个时...

2015-08-28

0 284

HDU1532（最大流模版题ek/dinic/isap）

就是由于下大雨的时候约翰的农场就会被雨水给淹没，无奈下约翰不得不修建水沟，而且是网络水沟，并且聪明的约翰还控制了水的流速，本题就是让你求出最大流速，无疑要运用到求最大流了。题中N为水沟数，M为水沟的顶点，接下来Si,Ei,Ci分别是水沟的起点，终点以及其容量。求源点1到终点M的最大流速。 ek: ...

2015-08-26

0 551

HDU1385 Minimum Transport Cost（最短路输出字典序路径floyd/逆序spfa）

题意：先给你一张你n * n的图，代表城市间的距离，然后，给出n个tax的费用，然后很多询问，问你a到b的最少费用，并且打印路径（字典序）注意tax的费用起点和终点不算 floyd求字典序路径: /* ******************************************...

2015-08-26

0 396

HDU2680 Choose the best route

题目大意：一个笨蛋要坐车去朋友家，但坐车呕吐，所以想在最短时间内到达。测试数据意思：第一行三个数：n(车站的个数，n<1000) | m(代表车站之间所有线路的总个数) | s(代表离朋友家最近的车站) 下面有m行: p q t 意思是：一条从p到q的线路，花费t时间 ...

2015-08-25

0 504

HDU2544 最短路（模版题dijkstra/floyd/spfa）

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

2015-08-24

0 360

HDU2899 Strange fuction（简单三分）

Problem Description Now, here is a fuction: F(x) = 6 * x^7+8*x^6+7*x^3+5*x^2-y*x (0 <= x <=100) Can you find the mi...

2015-08-23

0 622

HDU1233 还是畅通工程（模版题（prim+kruskal）两种模版）

Problem Description 某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。 In...

2015-08-23

0 470