昂贵的聘礼——dijkstra+枚举区间

时间  2020-08-22 标签 昂贵 聘礼 dijkstra 枚举 区间

1、题目

年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，因而便向酋长去求亲。酋长要他用10000个金币做为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长下降要求。酋长说："嗯，若是你可以替我弄到大祭司的皮袄，我能够只要8000金币。若是你可以弄来他的水晶球，那么只要5000金币就好了。“探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其余的东西，他能够下降价格。探险家因而又跑到其余地方，其余人也提出了相似的要求，或者直接用金币换，或者找到其余东西就能够下降价格。不过探险家不必用多样东西去换同样东西，由于不会获得更低的价格。探险家如今很须要你的帮忙，让他用最少的金币娶到本身的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过必定限制的两我的之间不会进行任何形式的直接接触，包括交易。他是一个外来人，因此能够不受这些限制。可是若是他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等因而间接接触，反过来也同样。所以你须要在考虑全部的状况之后给他提供一个最好的方案。
为了方便起见，咱们把全部的物品从1开始进行编号，酋长的允诺也看做一个物品，而且编号老是1。每一个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的"优惠"Vi。若是两人地位等级差距超过了M，就不能"间接交易”。你必须根据这些数据来计算出探险家最少须要多少金币才能娶到酋长的女儿。
 html

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

Output
输出最少须要的金币数。c++

Sample Inputweb

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

Sample Output算法

5250

2、思路

  • 创建一个超级源点0，从0创建一条边到每一个物品，权值为物品的价值。表明花费多少钱就能够购买这个物品。
     app

  • 若某个物品拥有替代品，表明从替代品创建一条边到这个物品，价值为替代的价值。 表明我有了这个替代品，那么还须要花费多少就能买这个物品。
     
    在这里插入图片描述svg

  • 最后就是等级制度。咱们能够枚举每一个等级区间，每次求最短路是只能更新在这个区间里面的物品。枚举全部状况求一个最小值就能够了。 特别注意的是区间必须包含1点。 那么范围就是【L[1] - m, L[1]】
     
    参考自https://xiaoxiaoh.blog.csdn.net/article/details/104198067spa

  • 关于等级制度的处理。对于从u点出发到w点的路径种，他会跟不少等级的人交易，然而必须知足在路径中的点等级不超过一个M值。从题意中咱们知道，最后全部的最短路都会聚集在1号点，也就是说1号点是全部最短路径存在的点，根据这个结论咱们依据1号点来给定区间。假设1号点等级为lev，那么也就是说在全部最短的这些点必须知足在 [ l e v − m , l e v + m ] [lev-m,lev+m] 这个区间里面。可是这个区间是不符合规范的，这个区间里面包含有子区间超过M长度的（显然这是存在的），因此咱们要继续缩小能够取到的区间。最终整个这个大区间能够分解成这样的小区间： [ l e v − m , l e v ] , [ l e v − m + 1 , l e v + 1 ] , [ l e v − m + 1 , l e v + 2 ] … [ l e v , l e v + m ] [lev-m,lev],[lev-m+1,lev+1],[lev-m+1,lev+2]\dots[lev,lev+m] ,由于这些区间都是大区间的子区间，因此是一定知足大区间的条件，在这些区间里面筛选最短路径就不会超出题目所规定的“等级”。
     .net

  • 例：假设酋长的等级是5，等级限制是2。那么须要枚举的区间就是 3~ 5，4~ 6，5~7code

  • 算法使用的是dijkstra算法，存图用的是链式前向星存图（固然也能够用其余方法存图）
     

c++代码

#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 500,INF = 0x3f3f3f3f;

int head[MAX],d[MAX],L[MAX],maxl=INF,len=1,M,N,P,X,T,V;
bool use[MAX];

struct Map
{
    int to,w,next;
}edge[MAX];


void add(int u,int v,int w)
{
    edge[len].w = w;
    edge[len].to = v;
    edge[len].next = head[u];
    head[u] = len++;
}

void dijkstra(int l,int r)
{
    memset(d,0x3f,sizeof(d));
    d[0] = 0;
    queue<int> q;
    q.push(0);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        use[u] = false;
        for(int j=head[u];j;j = edge[j].next)
        {
            int v = edge[j].to;
            int w = edge[j].w + d[u];
            if(l<=L[v] && L[v] <= r && d[v]>w)  // 若是这个点的等级在容许的范围内而且它的当前值要比更新后的值要大，咱们将它更新
            {
                d[v] = w;
                if(!use[v]) // 标记改点已经用过，避免重复搜索
                {
                    use[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

int main()
{
    scanf("%d %d",&M,&N);
    for(int u=1;u<=N;u++)
    {
        scanf("%d%d%d",&P,&L[u],&X);
        maxl = max(maxl,L[u]);
        add(0,u,P);
        while(X--)
        {
            scanf("%d%d",&T,&V);
            add(T,u,V);
        }
    }
    
    int ans = INF;
    for(int i=L[1]-M;i<=L[1];i++)  // 枚举区间能够取到的区间
    {
        dijkstra(i,i+M);
        ans = min(d[1], ans);    // 每搜索完一次更新一次最小金币
    }
    printf("%d",ans);
    return 0;
}

 

用邻接表存图(我的以为此方法更优)

#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;

const int INF = 0x3f3f3f3f,MAX_V = 500;
int M,N,C,X,T,A,L[MAX_V],d[MAX_V];

typedef pair<int,int> P;
int V=1;

struct edge
{
    int to,cost;
};
vector<edge> G[MAX_V];

void dijkstra(int l,int r)
{
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d,d+MAX_V,INF);
    d[0] = 0;
    que.push(P(0,0));

    while(!que.empty())
    {
        P p = que.top(); que.pop();
        int v = p.second;
        if(d[v] < p.first) continue;
        for(int i = 0;i<G[v].size();i++)
        {
            edge e = G[v][i];
            int w = e.cost;
            if(l <= L[e.to] && L[e.to] <= r && d[e.to] > d[v] + w)
            {
                d[e.to] = d[v] + w;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}

int main()
{
    scanf("%d%d",&M,&N);
    for(int u=1;u<=N;u++)
    {
        scanf("%d%d%d",&C,&L[u],&X);
        V++;
        G[0].push_back({u,C});
        while(X--)
        {
            scanf("%d%d",&T,&A);
            G[T].push_back({u,A});
            V++;
        }
    }

    int ans = INF;
    for(int i=L[1]-M;i<=L[1];i++)
    {
        dijkstra(i,i+M);
        ans = min(ans,d[1]);
    }
    printf("%d\n",ans);
    
    return 0;
}
联系我们 沪ICP备2021010478号-7