happy_lcj

题意：探险家想娶酋长的女儿，需要昂贵的聘礼，但可以用其他物品加优惠价替代，其他物品也可用另外的物品和优惠价替代，求探险家最少需多少金币可以娶到酋长的女儿？注意：等级限制：如果两人地位等级差距超过了M，就不能"间接交易"，但酋长的等级不一定最高分析：这是一道求有等级限制的最短路，可以将每个物品（包括酋长允诺）看成一个结点，替代品间的优惠价为边的权值，

题意：给定n中货币，以及它们之间的税率，A货币转化为B货币的公式为 B=(V-Cab)*Rab,其中V为A的货币量，求货币S通过若干此转换，再转换为原本的货币时是否会增加分析：这个题就是判断是否存在正权回路，可以用bellman-ford算法，不过松弛条件相反也可以用SPFA算法，判断经过转换后，转换为原本货币的值是否比原值大、、、

题意：n个珠子，给定它们之间的重量关系，按重量排序，求确定肯定不排在中间的珠子的个数分析：因为n为奇数，中间为(n+1)/2，对于某个珠子，若有至少有(n+1)/2个珠子比它重或轻，则它肯定不排在中间可以将能不能确定的权值初始化为0，能确定重量关系的权值设为1

题意：给定n头牛，以及某些牛之间的强弱关系，按强弱排序，求能确定名次的牛的数量思路：对于某头牛，若比它强和比它弱的牛的数量为 n-1,则他的名次可以确定

题意：输入n个经纪人，以及他们之间传播谣言所需的时间，问从哪个人开始传播使得所有人知道所需时间最少，这个最少时间是多少分析：因为谣言传播是同时的，对于某条路径使得所有人都知道的时间，不是时间的总和，而是路径中最长的边从多条路径的最长边，找出最小值，因为为多源最短路，用Floyd比较方便

题意：一个famer有一些农场，这些农场里面有一些田地，田地里面有一些虫洞，田地和田地之间有路(双向的)，即从a到b和从b到a时间都为c.虫洞的性质：时间倒流。即通过虫洞从a到b所花时间为 -c（单向的）.问从某块田出发，他能否通过虫洞的性质回到出发点前

题意：首先给出N中货币，然后给出了这N种货币之间的兑换的兑换率。如 USDollar 0.5 BritishPound 表示 ：1 USDollar兑换成0.5 BritishPound。问在这N种货币中是否存在货币经过若干次兑换后，兑换成原来的货币可以使货币量增加。思路：本题其实是Floyd的变形。将变换率作为构成图的路径的权值。不过构成的图是一个有向图。最后将松弛操作变换为:if(dis[i][j]<dis[i][k]*dis[k][j])。

题意：给出青蛙A,B和若干石头的坐标，现青蛙A想到青蛙B那，A可通过任意石头到达B, 问从A到B多条路径中的最长边中的最短距离分析：这题是最短路的变形，以前求的是路径总长的最小值，而此题是通路中最长边的最小值，每条边的权值可以通过坐标算出，因为是单源起点，直接用SPFA算法或dijkstra算法就可以了

Input输入数据有多组，每组的第一行是公交车的总数N(0<=N<=10000)；第二行有徐总的所在地start，他的目的地end；接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。note：一组数据中地名数不会超过150个。如果N==-1，表示输入结束。这个题输入的站名都是字符串，所以多一步对字符串的处理，但是要注意起点和终点可能相同的情况

链接： hdu 2066分析：每次以一个邻近的城市为起点，求所有能到达想去城市的最短时间

题意：在电梯的第i层只能上ki层或下ki层，但是不能到达低于一层或高于n层，给定起点与终点，要求出最少要按几次键分析：这题可以用BFS从上下两个方向搜索，也可以用最短路径若用最短路，则应将邻接矩阵中能到达的边的权值赋为1,这样就转化为了基本的最短路

题意：有编号1～P的站点， 有Q条公交车路线，公交车路线只从一个起点站直接到达终点站，是单向的，每条路线有它自己的车费。有P个志愿者早上从1站点出发，每个人要到达一个不同公交站点，（即一个站点有一个人）然后到了晚上再返回点1。求所有人来回的最小费用之和。分析：去的费用是从1站点出发的总和，直接正向建图 回来的费用是从各站点返回的到1站点的费用总和，如果一个一个求，会超时，所以要反向建图