2112专题
poj 2112 网络流+二分
题意： k台挤奶机，c头牛，每台挤奶机可以挤m头牛。 现在给出每只牛到挤奶机的距离矩阵，求最小化牛的最大路程。 解析： 最大值最小化，最小值最大化，用二分来做。 先求出两点之间的最短距离。 然后二分匹配牛到挤奶机的最大路程，匹配中的判断是在这个最大路程下，是否牛的数量达到c只。 如何求牛的数量呢，用网络流来做。 从源点到牛引一条容量为1的边，然后挤奶机到汇点引一条容量为m的边
HDU 2112 Today (Dijkstra)
http://acm.hdu.edu.cn/showproblem.php?pid=2112 HDU Today Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 16490 Accepted Submission(s): 3
ZOJ 2112 Dynamic Rankings (动态区间第K大) （线段树套SBT+二分）
题目：支持修改数组元素的区间第k大。 看题解这道题是可以用树状数组套主席树做的，但是树状数组套主席树不优化空间的话，要140MB左右，这题只给了32MB。 没看懂怎么优化，只能用线段树套平衡树了，我写的是线段树套SBT，线段树的每个节点上的SBT存这个节点代表的区间的所有数。 修改操作就是对于叶节点到根的所有SBT删除旧元素再加入新元素，删除的元素把下标入栈，插入元素时优先从栈中取。
fzu 2112 Tickets(欧拉道路）
题目链接：fzu 2112 Tickets 题目大意：给出n和m，表示有n个城市和m张票，现在要进行一场旅行，要求将所有的票使用掉，问还需要自己买几张票。 解题思路：欧拉道路的题目，只要输入中出现的城市才需要去考虑它的度数，并且要考虑说两个图是否联通。 我的做法是，读入数据的时候，标记出现过的点，并且记录每个点的度数，并查集记录点属于哪一个集合。 然后首先保证每个子的联通
POJ 2112 Optimal Milking (二分+匈牙利）
题意：在一片草场上有K台挤奶机，每台挤奶机最多可以为M头奶牛挤奶。有C头奶牛。把奶牛和挤奶机看做个体，则所有个体之间有一定的距离。现在给出K,C,M以及所有个体之间的距离。在保证所有奶牛都可以挤奶的情况下，求路程最长的奶牛的最小路程。 题解: 题目已经保证了所有奶牛都可以挤奶，那么最长的路径自然是 （顶点数-1） * 200。我们只需要二分最小路程，然后判断在此情况下是否所有的奶牛都存在合适的匹配
#分块，二分#zoj 2112 Dynamic Rankings
题目 支持修改的区间动态第k小 分析 树状数组套主席树（主席树不支持单点修改）太麻烦了，所以就用一种虽然时间略长但是比较简短的代码，当然运用到大段维护，小段朴素的方法，具体就是二分答案，其实理解上去还是比较简单的 代码 #include <cstdio>#include <cmath>#include <algorithm>#define rr register#defi
HDU 2112——HDU Today
最小路径的题目，地名的处理是把各个地名标记序号即可。 需要注意的是这题是的公交起点站可到终点站，终点站也可到起点站。另外给出两个相同地点时，输出是0. #include<iostream>#include<cstdio>#include<cstring>using namespace std;#define INF 1000000int map[160][160],dis[160
hdu 2112 HDU Today（Dijtktra+map）
HDU Today Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 31939 Accepted Submission(s): 7781 Problem Description 经过锦囊相助，海东集团终于度
HDOJ 2112 HDU Today （最短路 Dijkstra SPFA）
HDU Today Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 19468 Accepted Submission(s): 4573 Problem Description 经过锦囊
http://acm.hdu.edu.cn/showproblem.php?pid=2112
HDU Today Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 8239 Accepted Submission(s): 1957 Problem Description 经过锦囊相助，海东集团终于度过了危