注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

长风明志的博客

不要也不能做下一个谁,应该且可以做第一个自己

 
 
 

日志

 
 

【POJ1062】昂贵的聘礼  

2013-05-10 18:00:55|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 30635 Accepted: 8606

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值遍历所有的可能等级限制范围,如酋长的等级为3,M=1,则等级范围有:2~3、3~4,若酋长的等级为5,M=2,则等级范围可有:3~5、4~6、5~7。我们需要针对每一个范围从原图中构造一个子图(标志每个节点是否在该范围内),然后分别计算各个子图的酋长到冒险家的最短路径,去最小的值即可。

【POJ1062】昂贵的聘礼 - changfengmingzhi - 长风明志的博客
代码实现如下:
Memory: 252KTime: 0MS
Language: C++Result: Accepted

 #include <iostream>
#include <cmath>
#define MAXSIZE 102
#define INFINITE 999999999
using namespace std;
int* level=new int[MAXSIZE];
int* in_subgraph=new int[MAXSIZE];   //标志某个点是否在当前子图中
unsigned int (*matrix)[MAXSIZE]=new unsigned int[MAXSIZE][MAXSIZE];
unsigned int shortest_price(int N,int M,int a,int b)   //N为物品个数,M为等级限制,a,b分别为出发点和终止点
{
	unsigned int dist[MAXSIZE];
	bool accessed[MAXSIZE];
	unsigned short min_label;
	for(int i=1;i<=N+1;i++)
	{
		dist[i]=matrix[a][i];
		accessed[i]=false;
	}
	accessed[a]=true;
	while(1)
	{
		unsigned int minimum=INFINITE;
		min_label=a;
		for(int i=1;i<=N+1;i++)
		{
			if(in_subgraph[i]&&accessed[i]==false&&dist[i]<minimum)
			{
				minimum=dist[i];
				min_label=i;
			}
		}
		if(min_label==a)    //表示所有结点到起始点a的最短路径都已找到
		{
			break;
		}
		accessed[min_label]=true;
		for(int i=1;i<=N+1;i++)
		{
			if(in_subgraph[i]&&accessed[i]==false&&dist[i]>(dist[min_label]+matrix[min_label][i]))
			{
				dist[i]=dist[min_label]+matrix[min_label][i];
			}
		}
	}
	return dist[b];
}
int main()
{
	int M,N;
	unsigned int P,L,X,T,V;
	cin>>M>>N;
    for(int i=1;i<=N+1;i++)
	{
		for(int j=1;j<=N+1;j++)
		{
			matrix[i][j]=INFINITE;
		}
	}
	for(int i=1;i<=N;i++)
	{
		cin>>P>>L>>X;
        matrix[i][N+1]=P;     //该物品直接卖给探险家的金币价格
		level[i]=L;
		for(int j=1;j<=X;j++)
		{
			cin>>T>>V;
			matrix[i][T]=V;
		}
	}
	level[N+1]=level[1];
	unsigned int min_price=INFINITE;     //从各个子图中的最短路径值中选一个最小的值
	for(int i=0;i<=M;i++)     //处理每一个等级范围,如酋长的等级为5,M=2,则范围有3-5,4-6,5-7
	{
        //memset(in_subgraph,0,sizeof(in_subgraph));  //初始化所有结点都不在该子图中(满足某个等级范围限制)
		for(int j=1;j<=N+1;j++)
		{
			in_subgraph[j]=0;
		}
		for(int j=1;j<=N+1;j++)    //挑选结点到该子图中
		{
            if(level[j]>=level[1]-M+i&&level[j]<=level[1]+i)
			{
				in_subgraph[j]=1;
			}
		}
		unsigned int tempResult=shortest_price(N,M,1,N+1);
		if(tempResult<min_price)
		{
			min_price=tempResult;
		}
	}
	cout<<min_price<<endl;
	return 0;
}
  评论这张
 
阅读(448)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017