POJ_2031_建图+kruskal POJ 2031 思路:先将每个点位置都存起来,然后给每个点建边,2个球的半径超过圆心之间的距离就边为0,否则边就是圆表面之间的距离 kruskal 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465 2019-07-15 算法 kruskal
prim和kruskal模板 两种都是基于贪心思想的算法 prim12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include <bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;const int maxn 2019-07-15 算法 模板
POJ_1251_kruskal POJ 1251 处理输入输出格式+kruskal12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include <iostream>#include <algorithm>using namespace std; 2019-07-15 算法 kruskal
POJ_1062_最短路变形 POJ 1062 题意： 替换就相当于一条指向另一个点的有向边,权值是价值,但是每个点都有等级作为限制条件, 限制条件还必须在一个范围,例如:level[1] = 3 m=1,节点等级限制范围:[2,3]、[3,4],level[1] = 3 m=2, 范围：[1,3]、[2,4],[3,5] 每次最短路在将不再范围的点排除,然后取每个范围中最短的点. 12345 2019-07-15 算法
POJ_1847_思维最短路 POJ 1847 思路：每一个点都有多个出路,默认指出一条,问是否有最少转化次数到达终点, 条件转化为,原点的第一条边的权值为0,其余出边的权值为1,等价于转换开关的次数. 最短路模板123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#inclu 2019-07-15 算法
shell变量+处理字符工具 \放在命令最后表示连接下一行 变量规则 Bash中变量默认的是字符串型,如要进行数值运算,需要修改变量的类型,指定为数值型 变量赋值等号两边不能有空格变量分类 用户自定义变量 环境变量,保存操作系统环境相关数据 预定义变量,(相当于脚本传入变量) set 打印系统所有变量 unset name 变量删除 unset time PATH系统查找命令的路径临时修改环境变量PATH=&q 2019-07-14 Linux学习 awk cut sed
HDU_4725_思维建图+最短路 HDU 4725 难点是如何将楼层转化到图中, 用2个点将一个面(楼层)抽象出来,1个入点,1个出点 一个面上的所有点都指向出点,权值为0 入点指向该面所有的点(除了出点),权值为0 入点指向出点,权值为0, 中间的楼层的出点分别指向上一层的入点和下一层的入点,权值为c.将所有楼层都连接起来 没有最短路则dist[n] = MAX dij1234567891011121314151617 2019-07-10 算法
HDU_4370_思维建图+spfa HDU 4370 思维题目,将条件转化成最短路来做,观察题目条件. 求$\Sigma c_{ij}*x_{ij}$,等价于常数乘以边的权值,恰恰这些常数是只能是0/1,所以只能是边的组合. 条件1：起始点1到其余每个点中的任意一个点可以有一条边,出度为1. 条件2：其余每一个点中的中任意一个点到终点4(n)可以有一条边,入度为1. 条件3：观察下标发现2 - 3之间的点到源点和终点常数都相同 2019-07-10 算法
POJ_3169_差分约束转最短路 POJ 3169 差分约束问题转化为最短路 由最短路三角形关系得到dist[u] + w >= dist[v]->dist[v] <= dist[u] + w,则说明dist[]已经是源点到个点之间的距离了.w是u指向v这条有向边的权值. 将牛的关系表达为不等式,然后建图, dist[j] - dist[i] <= k -> dist[j] <= di 2019-07-10 算法
POJ_2502_建图+最短路 POJ 2502 感觉题目意思不清晰,主要是建图,然后是最短路. 首先将速度换算成分钟,将所有输入的点都离散一下,然后处理-1 -1与一条地铁路线之间的时间(双向). 然后处理不同地铁路线之间点的距离 grid[i][j] = grid[j][i] = min(grid[i][j],dis(point[i],point[j])/v1) 1234567891011121314151617 2019-07-09 算法