//最短路径
POJ1860:题目链接
大意:给定初始货币,给一些货币兑换点,每个货币兑换点可将货币A以E1的汇率和V1的手续费兑换成货币B,和将货币B以E2的汇率和V2的手续费兑换成货币A,给定初始所在货币点,问初始货币能否在一系列兑换后回到初始所在货币点时的价值增大?(这不是套汇么。。)
分析:这题可以用bellman-ford的思想来解,bellman-ford在最短路求完后,最后一步处理如遇到负权边仍会更新最小值,同理,用bellman-ford求最长路径时,如果图中有一条正权环路,那么在最后一步处理时仍会更新最大值,不断更新后再回到初始点就能达到题目的要求了。因此根据输入数据建图,做一遍反向的bellman-ford判断即可。
POJ3259:题目链接
大意:给定一个有向图,边权可正可负,问能否找出一条环路,使得边权为负?
分析:同上,简单的bellman-ford判定即可
POJ1062:题目链接
大意:给定一些点,每个点有相应的编号、价值和等级,对于每个点给定与之相邻的点和边的权值(有向边),求一条以1号点为终点的最短路径,且这条路上点的等级之差不能大于给定的M。
分析:设一个0号点与每个点相连,边的权值为每个点的价值,枚举每一个点作为等级最高的点,将等级比其低且等级差不超过M的的点加入路径,做一遍Dijkstra,每次求得的Dist[1]与最小值比较,得出最小值。
代码:(转自 優YoU http://user.qzone.qq.com/289065406/blog/1299338542)
//Memory Time
//300K 32MS #include<iostream>
using namespace std; const int inf=0x7fffffff; //无限大 int M,N;//M为等级差,N为物品数目
int price[][]; //物品i在有第t号替代品情况下的优惠价pricr[t][i],当t=0时说明i无替代品,此时为原价
int lv[]; //第i号物品主人的等级lv[i]
int x[];//第i号物品的替代品总数x[i] int dist[];//最初的源点0到任意点i的最初距离(权值),相当于每个物品的原价 bool vist[]; //记录点i是否已被访问 /*Initial and Input*/ void data_init()
{
memset(price,,sizeof(price));
memset(lv,,sizeof(lv));
memset(dist,inf,sizeof(dist));
memset(vist,false,sizeof(vist)); cin>>M>>N;
for(int i=;i<=N;i++)
{
cin>>price[][i]>>lv[i]>>x[i]; //price[0][i]物品i无替代品时的原价 for(int j=;j<=x[i];j++)
{
int t,u; //t替代品编号,u优惠价(临时变量)
cin>>t>>u;
price[t][i]=u; //物品i在有第t号替代品情况下的优惠价,即点t到点i的权值
}
}
} /*Dijkstra Algorithm*/ int dijkstra()
{ int node;//记录与当前源点距离最短的点
int sd;//最短距离
int i,j; for(i=;i<=N;i++)
dist[i]=price[][i]; //假设最初的源点就是0点,初始化最初源点到各点的权值dist[i] for(i=;i<=N;i++) //由于1点是目标点,因此最坏的打算是进行n次寻找源点到其他点的最短路,并合并这两点(不再访问相当于合并了)
{
node=;
sd=inf;
for(j=;j<=N;j++)
{
if(!vist[j] && sd>dist[j]) //在未访问的点中,寻找最短的一条
{
sd=dist[j];
node=j; //记录该点
}
}
if(node==) //若node没有变化,说明所有点都被访问,最短路寻找完毕
break; vist[node]=true; //记录node点已被访问
for(j=;j<=N;j++)
{
if(!vist[j] && price[node][j] > && dist[j] > dist[node] + price[node][j]) //把未访问但与node(新源点)连通的点进行松弛
dist[j]=dist[node]+price[node][j];
}
}
return dist[]; //返回当前次交易后目标点1在等级lv[i]约束下的最短距离
} int main()
{
data_init(); //初始化并输入数据 int temp_price; //当前次交易后目标点1在等级lv[i]约束下的最少价格
int maxlv; //最大等级(酉长的等级不一定是最大的)
int minprice=inf; //最低价格(初始化为无限大) for(int i=;i<=N;i++)
{
/*在等级限制下,寻找允许被当前点访问的点*/ maxlv=lv[i]; //把当前物品的等级暂时看做最高等级
for(int j=;j<=N;j++) //遍历其他各点
{
if(lv[j]>maxlv || maxlv-lv[j]>M) //当其它物品j的等级比当前物品高(保证单向性),或者两者等级之差超出限制M时
vist[j]=true; //物品j则强制定义为“已访问”状态,不参与后续操作
else
vist[j]=false; //否则物品j定义为“未访问”状态,参与后续操作
} temp_price=dijkstra(); //记录当前次交易后目标点1在等级lv[i]约束下的最短距离(最少价格) if(minprice>temp_price) //寻找各次交易后的最少价格,最终确认最少价格
minprice=temp_price;
}
cout<<minprice<<endl; return ;
}
POJ2253:题目链接
大意:给定一些点(坐标),源点(点1)和终点(点2),求一条从源点到终点的路径,使得这条路径上最长两点之间的距离最短。
分析:
解法一:构图,成边,求出最长两点的距离,二分距离,将小于该二分距离的边加入边集判断两点能否到达,若能则缩小距离,若不能则增大距离。//暂未实现
解法二:floyed变种。求任意两点之间的距离,依次枚举k点,i点,j点,若max(dist[i][k],dist[k][j]) < dist[i][j]则更新dist[i][j]为两者中最大值,答案为dist[1][2];
解法三:Dijkstra,同理,更新最大值改为更新最小值即可。
POJ1125:题目链接
大意:给定n个点和有向边,每个点可以散布一条消息到其相邻点,花费边权的时间,问从哪个点开始散布消息,使得最后一个收到消息的时间最短,求此点和最后一个人收到消息的时间。
分析:floyed求出每对点之间的最短路径,之后枚举每个点,枚举它到剩下点的最短路径,取个最大值,最后在这些最大值中取个最小值。
POJ2240:题目链接
大意:简化版的POJ1860,给一些货币和他们之间的兑换比率,问是否存在套汇的可能
分析:
解法一:枚举每种货币,给定其初始单位1,做一遍bellman-ford,判断是否存在到自身的正权环路,若有一个点存在则输出YES,否则输出NO。
解法二:floyed求最长路径,枚举f[i][i]是否大于1,存在则输出YES。
//最小生成树
POJ1789:题目链接
大意:用一个7位的string代表一个编号,两个编号之间的d代表这两个编号之间不同字母的个数。一个编号只能由另一个编号“衍生”出来,代价是这两个编号之间相应的d,现在要找出一个“衍生”方案,使得总代价最小,也就是d之和最小。
分析:任意两个字符串都连边构成一个完全图,权值为两个字符串计算后的d,要求衍生出所有点边权和最小,就是求图的最小生成树,此图为稠密图,用Prim算法即可
POJ2485:题目链接
大意:给一些城市,和这些城市之间的距离,问怎样建造高速公路(双向),使得任意两个城市都能互相到达,且所造距离最短。
分析:裸的最小生成树问题,注意是稠密图,使用Prim算法。
POJ1258:题目链接
大意:给一些农庄连上网,给出任意两个农庄之间相连的花费,问使得所有农庄都连上网最少要花费多少
分析:同2485;
POJ3026:题目链接
大意:给一个N*M的迷宫,#处不能走,空白处可以走,S是起始点,x个A是目标,有x个人从S点出发到所有A点,共同走过的路径只算一次,问从S点到达所有A点走的路最短是多少。
分析:枚举每个有效点(S和A),BFS出到其他所有点最短距离,这一过程完成后对形成的图做Prim,即题目所求。
//拓扑排序
POJ1094:题目链接
大意:给定一系列关系,问是否在给一组关系后,能够判断所给关系是矛盾的,或者能找出唯一符合这样关系的组合,或是最终也无法确定他们的关系。
分析:(转自http://www.cppblog.com/infinity/archive/2008/11/06/66086.html)
方法 拓扑排序
每次读入一对关后,做一次floyd, 计算传递闭包.
然后判环,其实很简单,就是看有没有点i的map[i][i]=1;
有就证明有环!如果有环就矛盾了。
如果无环再判断是否能确定关系,(注意每次都把出入度数组清零!)计算每个点的出度+入度是否=n-1;
如果所有点都有这个关系,那么唯一的关系就确定了,接下来拓扑排序就能找出这个关系.
总结:虽然这些题目很基础,但考察了一些基础算法的变种,例如bellman-ford对正权环路和负权环路检测的应用,floyed求路径最大值最小和计算传递闭包,Dijkstra算法的修改,拓扑排序唯一性的判断。明天白天主要完成树形DP7题巩固自己的树形DP知识,希望自己能做到!