POJ1062 [ZJOI2002]昂贵的聘礼 题解【最短路】【枚举】

作者: wjyyy 分类: 最短路,枚举,解题报告 发布时间: 2018-06-27 21:47

点击量:17

 

   最短路的变式:有限制条件的最短路

 

Description

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

Input

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

Output

输出最少需要的金币数。

Sample Input

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

 

   这个题可以看出来能用图论建模,不过有个等级限制。我们需要做的就是利用好这个等级限制来跑最短路。那么这个等级限制是波动的,也就是说,当m为2时,到过等级为3的点,也可以同时到等级为2和等级为4的点,或者等级为1,2,或等级为4,5的点。这些情况都是合法的,当然在m很大的情况下枚举合法状态当然是不可取的,如果不枚举状态就会变多从而不合法。

 

   我们可以换一种思路,首先,因为在这个图上,任意两点可以互达,只是有没有优惠的区别。建立n×(n-1)条普通有向边(权值为边终点的费用),以及若干条($latex\sum_{i=1}^{n}T_i$)特殊有向边,权值为优惠价格。因为每件物品的一个优惠只会用掉一个物品,所以我们这样建图是可以解决这个问题的。那么我们可以从任何一个点出发,以酋长1号为终点,这样我们在这个稠密图里有了各种各样的情况,出发点任意定,就可以相对任性地控制等级限制了。这样我们只要枚举每个长度为m的范围,无论从哪个点出发,我们只管在这个范围内的点跑最短路,就一定是合法的解了。不过如果每个人的等级跨度太大,枚举全部太过浪费,我们只需要以每个点为上界或下界(只用一种,但所有点必须统一用一种),枚举n次,就能包含所有范围。因为这n次涵盖了最小值和最大值,那么就是比较完备的状态了。

 

   SPFA求最短路的过程可以是建立起点0,把0向每个点连一条边,也可以像我一样每次SPFA把所有点都进队,根据限制条件跑一遍(特别要注意的是,每次进队是也是要判断是否在范围内这个条件的,错了这一点特别可惜),这个题是没有严格起点的,所以定某个点为起点可能是错误的。

 

   一道比较经典的最短路建模+限制条件题,只要理清题意,多试做法,就可以建出最短路的模型来。

 

#include<cstdio>
#include<cstring>
#include<deque>
using std::deque;
struct node
{
    int n,v;
    node *nxt;
    node(int n,int v)
    {
        this->n=n;
        this->v=v;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[105],*tail[105];
int obj[105],lev[105],m;
bool used[105];
int dis[105],n;
void spfa(int d)
{
    memset(used,1,sizeof(used));
    memset(dis,0x3f,sizeof(dis));
    deque<int> q;
    for(int i=1;i<=n;i++)//把所有符合条件的点入队
    {
        if(lev[i]<d-m||lev[i]>d)
            continue;
        q.push_back(i);
        dis[i]=obj[i];
    }
    while(!q.empty())
    {
        int k=q.front();
        q.pop_front();
        used[k]=false;
        node *p=&head[k];
        while(p->nxt!=NULL)
        {
            p=p->nxt;
            if(lev[p->n]<d-m||lev[p->n]>d)
                continue;
            if(dis[p->n]>dis[k]+p->v)
            {
                dis[p->n]=dis[k]+p->v;
                if(!used[p->n])
                {
                    used[p->n]=true;
                    if(q.empty()||dis[p->n]<q.front())
                        q.push_front(p->n);
                    else
                        q.push_back(p->n);
                }
            }
        }
        //额外做一次 不优惠
        for(int i=1;i<=n;i++)
        {
            if(lev[i]<d-m||lev[i]>d)
                continue;
            if(dis[i]>dis[k]+obj[i])
            {
                dis[i]=dis[k]+obj[i];
                if(!used[i])
                {
                    used[i]=true;
                    if(q.empty()||dis[i]<q.front())
                        q.push_front(i);
                    else
                        q.push_back(i);
                }
            }
        }

    }
    return;
}
int main()
{
    int u,v,w;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        tail[i]=&head[i];
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&obj[i],&lev[i],&u);
        for(int j=1;j<=u;j++)
        {
            scanf("%d%d",&v,&w);
            tail[v]->nxt=new node(i,w);
            tail[v]=tail[v]->nxt;
        }
    }
    int ans=obj[1];
    for(int i=1;i<=n;i++)
    {
        spfa(lev[i]);
        ans=dis[1]<ans?dis[1]:ans;//更新答案
    }
    printf("%d\n",ans);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */