首页 > 专题系列 > Java解POJ > POJ 1062 昂贵的聘礼 [解题报告] Java
2013
11-09

POJ 1062 昂贵的聘礼 [解题报告] Java

昂贵的聘礼

问题描述 :

年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了,于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币,便请求酋长降低要求。酋长说:”嗯,如果你能够替我弄到大祭司的皮袄,我可以只要8000金币。如果你能够弄来他的水晶球,那么只要5000金币就行了。”探险家就跑到大祭司那里,向他要求皮袄或水晶球,大祭司要他用金币来换,或者替他弄来其他的东西,他可以降低价格。探险家于是又跑到其他地方,其他人也提出了类似的要求,或者直接用金币换,或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西,因为不会得到更低的价格。探险家现在很需要你的帮忙,让他用最少的金币娶到自己的心上人。另外他要告诉你的是,在这个部落里,等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触,包括交易。他是一个外来人,所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易,地位较高的的人不会再和他交易,他们认为这样等于是间接接触,反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。

为了方便起见,我们把所有的物品从1开始进行编号,酋长的允诺也看作一个物品,并且编号总是1。每个物品都有对应的价格P,主人的地位等级L,以及一系列的替代品Ti和该替代品所对应的”优惠”Vi。如果两人地位等级差距超过了M,就不能”间接交易”。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。

输入:

输入第一行是两个整数M,N(1 <= N <= 100),依次表示地位等级差距限制和物品的总数。接下来按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是三个非负整数P、L、X(X < N),依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V,分别表示替代品的编号和"优惠价格"。

输出:

输出最少需要的金币数。

样例输入:

1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0

样例输出:

5250

解题代码:

//仿照别人的思想敲得,之前不是很了解dijkstra,做过这题后有些理解 
//1,将当前未纳入最短路的符合要求的距离最短结点纳入最短路; 
//2,将所有与当前纳入的结点有关联并且未被纳入最短路的结点最短距离进行更新。 
//图论中另一个求最小生成树的的经典算法Prim算法与Dij过程极其类似,都是贪心思想。 
//只是一个是对顶点的选择,另外一个是对边的选择。 

import java.util.*; 
public class Main 
{ public static int[][] e; 
   public static int[]  dis; 
   public static int[] used; 
   public static int[] level; 
   public static int n,m; 
   public static void main(String[] args){ 
    Scanner cin = new Scanner(System.in); 
    int  x,t; 
    e = new int[101][101]; 
    dis = new int[101]; 
    used =  new int[101]; 
    level = new int[101]; 
          m=cin.nextInt(); 
          n=cin.nextInt(); 
           for(int i=1;i<=n;i++) 
             {   e[0][i]=cin.nextInt(); 
                 level[i]=cin.nextInt(); 
                  x=cin.nextInt(); 
                for(int j=0;j< x;j++) 
                { t=cin.nextInt(); 
                  e[t][i]=cin.nextInt(); 
                } 
             } 
           solve(); 
} 

public static void solve() 
{ int max,result; 
  result=e[0][1]; 
  for(int i=1;i<=n;i++) 
     { max=level[i]; 
       for(int j=1;j<=n;j++) 
        if(level[j]>max || level[j]< max-m)//判断所交易的人的等级是否符合题目所述的条件 
         used[j]=1;//不符合 
        else 
         used[j]=0; //符合 
       dijkstra(); 
       if(result>dis[1]) //比较每次所求的费用 
         result=dis[1]; 
} 
System.out.println(result); 
} 
public static void dijkstra() 
{ int min,temp,k; 
  for(int i=1;i<=n;i++) 
   dis[i]=e[0][i]; 
  for(int i=1;i<=n;i++) 
     { min=0x7FFFFFFF; 
       k=0; 
       for(int j=1;j<=n;j++)//找出代价最小的边 
         if(used[j]==0 && dis[j]< min) 
          {min=dis[j]; 
              k=j; 
          } 
       if(k==0) 
        break; 
       used[k]=1; 
       for(int j=1;j<=n;j++)//更新其节点的值 
        if(used[j]==0 && e[k][j]>0 && min+e[k][j]< dis[j]) 
         dis[j]=min+e[k][j]; 
    } 
   } 
}