emerald's blog

sort -n:按数字排序,默认是按照字符串排序. -r:reverse反排序 -k a,b:排序的范围,第a到b列 -t ":":修改分隔符，例如:cp /etc/passwd /tmp/shsort -n -k 3,4 -t ":" student | awk 'BEGIN{FS=":"}{print $3 "

POJ 2031 思路:先将每个点位置都存起来,然后给每个点建边,2个球的半径超过圆心之间的距离就边为0,否则边就是圆表面之间的距离 kruskal 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566

两种都是基于贪心思想的算法 prim12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include <bits/stdc++.h>#define INF 0x3f3f3f3fusing namespace std;const int maxn = 1

POJ 1251 处理输入输出格式+kruskal12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include <iostream>#include <algorithm>using namespace std;co

POJ 1062 题意： 替换就相当于一条指向另一个点的有向边,权值是价值,但是每个点都有等级作为限制条件, 限制条件还必须在一个范围,例如:level[1] = 3 m=1,节点等级限制范围:[2,3]、[3,4],level[1] = 3 m=2, 范围：[1,3]、[2,4],[3,5] 每次最短路在将不再范围的点排除,然后取每个范围中最短的点. 12345678910111213

POJ 1847 思路：每一个点都有多个出路,默认指出一条,问是否有最少转化次数到达终点, 条件转化为,原点的第一条边的权值为0,其余出边的权值为1,等价于转换开关的次数. 最短路模板123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include

\放在命令最后表示连接下一行 变量规则 Bash中变量默认的是字符串型,如要进行数值运算,需要修改变量的类型,指定为数值型 变量赋值等号两边不能有空格 变量分类 用户自定义变量 环境变量,保存操作系统环境相关数据 预定义变量,(相当于脚本传入变量) set 打印系统所有变量 unset name 变量删除 unset time PATH系统查找命令的路径临时修改环境变量PATH

HDU 4725 难点是如何将楼层转化到图中, 用2个点将一个面(楼层)抽象出来,1个入点,1个出点 一个面上的所有点都指向出点,权值为0 入点指向该面所有的点(除了出点),权值为0 入点指向出点,权值为0, 中间的楼层的出点分别指向上一层的入点和下一层的入点,权值为c.将所有楼层都连接起来 没有最短路则dist[n] = MAX dij123456789101112131415161718

HDU 4370 思维题目,将条件转化成最短路来做,观察题目条件. 求$\Sigma c_{ij}*x_{ij}$,等价于常数乘以边的权值,恰恰这些常数是只能是0/1,所以只能是边的组合. 条件1：起始点1到其余每个点中的任意一个点可以有一条边,出度为1. 条件2：其余每一个点中的中任意一个点到终点4(n)可以有一条边,入度为1. 条件3：观察下标发现2 - 3之间的点到源点和终点常数都相同,说

POJ 3169 差分约束问题转化为最短路 由最短路三角形关系得到dist[u] + w >= dist[v]->dist[v] <= dist[u] + w,则说明dist[]已经是源点到个点之间的距离了.w是u指向v这条有向边的权值. 将牛的关系表达为不等式,然后建图, dist[j] - dist[i] <= k -> dist[j] <= dist