冰冻三尺 非一日之寒

摘要： 题意：。。。中文题。。。 昂贵的聘礼 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 54350 Accepted: 16368 Description 年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长 阅读全文

摘要： 差分约束系统 一、概念 如果一个系统由n个变量和m个约束条件组成，形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统。 二、引例 给定n个变量和m个不等式，每个不等式的形式为 x[i] - x[j] <= a[k] (0 <= i, j < n, 0 <= k 阅读全文

摘要： 概念： 传递一种关系，例如 a//b b//c 则 a//c 从已知的初始关系中 推出最后所有对象之间的关系 初始时把所有有关系的标记为1 即a[i][j] = 1 然后用Floyd 推出最后的结果 则有关系的两个对象被标记为1 例题：POJ3660 题意： n个牛打架 初始已知m个打架结果 求最后 阅读全文

摘要： 题意： 农夫john发现了一些虫洞，虫洞是一种在你到达虫洞之前把你送回目的地的一种方式，FJ的每个农场，由n块土地(编号为1-n),M 条路，和W个 虫洞组成，FJ想从一块土地开始，经过若干条路和虫洞，返回到他最初开始走的地方并且时间要在他离开之前，或者恰好等于他离开的时间。 把虫洞的时间看成负边权 阅读全文

摘要： 题意： 有n头牛去第x个点开party（有点高大上~），单向路，去到还得回来，问这n头牛每一头花费的总时间的最大值是多少 模板spfa： 阅读全文

摘要： 题意： 给出一张各种货币交换的网络，问在网络中交换原有的货币，问货币能否增值? 解析： 判断是否存在正环即可 用spfa 负环和正环的判定方法一样 如果一个点的进队次数超过n次 则存在环 代码如下： 阅读全文

摘要： 题意： 一个n * n 的棋盘 上面有些障碍物 放棋子 棋子不能在同一行 同一列 但可以在同一行或同一列隔着障碍物放 这题与poj1321 的思想差不多 对于一个位置 有两种状态放还是不放 参数inx 从1到n*n递增 inx/n表示x轴坐标 inx%n表示y轴坐标 k 为当前所用的棋子 阅读全文

摘要： 题意： 在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。 Input 输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开， 阅读全文

摘要： 题意：给出几个集合，每个集合中有Si个点 且任意两个点的距离为ti，现在要求两个人分别从1和n出发,问最短多长时间才能遇到,且给出这些可能的相遇点; 取两个人到达某点时所用时间大的值 然后取最小的 若有多个结果 则按点的升序排列 解析： 比较裸的最短路 ，但坑在建图上，Si的和小于1e6 那么建的边 阅读全文

摘要： 题意：有n个点，每个点都在一个层内，层与层之间的距离为c，一个层内的点可以到达与它相邻的前后两个层的点，还有m条小路 。。时间真的是卡的很恶心啊。。。 借一下别人的思路思路： 这题主要难在建图上，要将层抽象出来成为n个点（对应编号依次为n+1~n+n），然后层与层建边，点与点建边，层与在该层上的点建 阅读全文