POJ-1062-昂贵的聘礼（枚举）-白红宇

POJ-1062-昂贵的聘礼（枚举）

阅读量：6281 次

发布时间：2019-06-22

本文共 2250 字，大约阅读时间需要 7 分钟。

链接：https://vjudge.net/problem/POJ-1062

题意：

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

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

思路：

普通的最短路，但是因为有了等级差距的限制。

所有可以用的结点使用时不能互相差M，所以使用枚举，

令使用的level不超过国王等级的一定范围，但是中转点可能会超过。

所以，令国王等级为level，限制为m，枚举 i(0->m) 限制区间为(level-m+i,level+i)

Dijkstra使用时判定每个点即可。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                using namespace std;const int MAXN = 110;int n,m;int Map[MAXN][MAXN];int Level[MAXN];int Vis[MAXN];int Dis[MAXN];int D[MAXN];int Dijkstra(int left,int right){ for (int i = 1;i<=n+1;i++) D[i] = Dis[i]; Vis[1] = 1; for (int i = 1;i<=n+1;i++) { int w = -1,small = 99999999; for (int j = 1;j<=n+1;j++) { if (Vis[j] == 0&&Level[j] <= right&&Level[j] >= left&&small > D[j]) { w = j; small = D[j]; } } Vis[w] = 1; if (w == 2) break; for (int j = 1;j<=n+1;j++) { if (Vis[j] == 0 && Level[j] <= right && Level[j] >= left && D[j] > D[w] + Map[w][j]) { D[j] = D[w] + Map[w][j]; } } } return D[2];}int main(){ int money,level,num; int x,mm; scanf("%d%d",&m,&n); for (int i = 1;i<=n+1;i++) for (int j = 1;j<=n+1;j++) if (i == j) Map[i][j] = 0; else Map[i][j] = 99999999; for (int i = 2;i<=n+1;i++) { scanf("%d%d%d",&money,&level,&num); Level[i] = level; Map[1][i] = money; for (int j = 1;j<=num;j++) { scanf("%d%d",&x,&mm); Map[x+1][i] = mm; } } for (int i = 1;i<=n+1;i++) Dis[i] = Map[1][i]; int re = Dis[2]; for (int i = 0;i<=m;i++) { memset(Vis,0,sizeof(Vis)); re = min(Dijkstra(Level[2]-m+i,Level[2]+i),re); } printf("%d\n",re); return 0;}

转载于:https://www.cnblogs.com/YDDDD/p/10279766.html

你可能感兴趣的文章