【ACM/ICPC2013】POJ基础图论题简析（一）

前言：昨天contest4的惨败经历让我懂得要想在ACM领域拿到好成绩，必须要真正的下苦功夫，不能再浪了！暑假还有一半，还有时间！今天找了POJ的分类题库，做了简单题目类型中的图论专题，还剩下二分图和最大流两个子专题没有完成，将在简析（二）中放出。

//最短路径

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知识，希望自己能做到！