本文主要是介绍昂贵的聘礼 （dfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
昂贵的聘礼
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)
Total Submission(s) : 68 Accepted Submission(s) : 21
为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的"优惠"Vi。如果两人地位等级差距超过了M，就不能"间接交易"。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。
1 4 10000 3 2 2 8000 3 5000 1000 2 1 4 200 3000 2 1 4 200 50 2 0
5250
中文题，不解释。
思路：
用的dfs，看很多人都是用的图论的知识做的，有点懵。。。图论掌握的还是不扎实。。。下面附上dfs的代码吧：
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
using namespace std;
int mp[105][105],price[105],level[105],dis[105],vis[105];//mp代表的有关系的并且之间的价格，level代表等级，price代表优惠的价格，dis代表每一时刻价格，vis表示是否买过
int v,maxl,minl,p;
int M,N,P,L,X,minn;
void dfs(int pos){int i;int t_max,t_min;for(i=2;i<=N;i++){if(mp[pos][i]!=-1&&vis[i]==0){ //有关系并且未购买过if(dis[pos]+mp[pos][i]<=minn){ //条件if(level[i]<=maxl&&level[i]>=minl){t_max=maxl; //临时变量t_min=minl;maxl = level[i] + M> maxl? maxl : level[i] + M;minl = level[i] - M > minl ? level[i] - M : minl;dis[i] = dis[pos] + mp[pos][i];vis[i] = 1;dfs(i);vis[i] = 0;maxl = t_max;minl = t_min;}}}}if(minn > dis[pos] + price[pos]) //找最小值minn = dis[pos] + price[pos];
}
int main()
{ios::sync_with_stdio(false);//int M,N,P,L,X;int p,v;int i,j;cin>>M>>N;memset(mp,-1,sizeof(mp));memset(dis, 0,sizeof(dis));memset(vis,0,sizeof(vis));for(i=1;i<=N;i++){cin>>P>>L>>X;level[i]=L;price[i]=P;for(j=1;j<=X;j++){cin>>p>>v;mp[i][p]=v;}}maxl=level[1]+M;minl=level[1]-M;vis[1]=1;minn=price[1];dfs(1);cout<<minn<<endl;return 0;
}
枚举等级限制。以下转载
对于从u点出发到w点的路径中，他会跟很多等级的人交易，然而必须满足在路径中的点等级差不很超过一个M值，那么怎么对这样的问题求解呢？我没看报告前是很疑惑的！
假设如果给这条路径加上一个附加条件的话，情况可能就有所变化了，要求最短路中的所有点的等级在一个区间内[a,b]，如果能够很好的给出这个区间的话，只要对图中的点进行上筛选即可了。
这个区间的确定显然不是随便的，那么就要根据一定的条件了，从题意中我们知道，最后所有的最短路都会汇集在1号点，也就是说1号点是所有最短路都存在的点，好了，这个条件很重要，这样我们就可以依照1号点来给定区间了，比如1号点等级为lev，那么也就是说在所有最短路的这些点都必须满足在[lev-M,lev+M]这个区间里面。好了，可能你会迫不及待将这个区间作为最后的区间，在想想，如果在这个区间内出现的两个点的他们之间的等级差超过了M值（这是存在的），显然，不符合题意了，所以这个区间还有继续缩小。其实只要稍微动动脑子，就可以找出这样的区间[lev-M,lev],[lev-M+1,lev+1],... ...,[lev,lev+M]，首先这些区间都满足大区间的条件，而且如果将这些区间的某个作为筛选条件的话，在这个区间内的任意两个点的等级都不会超过M值，这就是很特别的地方了
#include <iostream>
using namespace std; #define INF 200000000 int map[110][110], n;
int rank[110], value[110], dist[110];
int mark[110], within[110]; int Dijkstra ()
{ int i, j, k, min; memset(mark,0,sizeof(mark)); for ( i = 1; i <= n; i++ ) dist[i] = map[1][i]; dist[1] = 0; mark[1] = 1; for ( i = 1; i <= n; i++ ) { min = INF; for ( j = 1; j <= n; j++ ) { if ( !mark[j] && within[j] && dist[j] < min ) { k = j; min = dist[j]; } } if( min == INF ) break; mark[k] = 1; dist[k] = min; for ( j = 1; j <= n; j++ ) if ( !mark[j] && within[j] && dist[k] + map[k][j] < dist[j] ) dist[j] = dist[k] + map[k][j]; } min = INF; for ( i = 1; i <= n; i++ ) if ( dist[i] + value[i] < min && mark[i] ) min = dist[i] + value[i]; return min;
} int main()
{ int ranklimit, t, i, j, k; cin >> ranklimit >> n; for ( i = 1; i <= n; i++ ) for ( j = 1; j <= n; j++ ) map[i][j] = ( i == j ? 0 : INF); for ( i = 1; i <= n; i++ ) { cin >> value[i] >> rank[i] >> t; for ( j = 0; j < t; j++ ) { cin >> k; cin >> map[i][k]; } } int chief = rank[1], min_cost = INF, cost; for ( i = 0; i <= ranklimit; i++ ) { memset(within,0,sizeof(within)); for ( j = 1; j <= n; j++ ) { if ( chief - rank[j] <= ranklimit - i && rank[j] - chief <= i) within[j] = 1; } cost = Dijkstra (); if ( cost < min_cost ) min_cost = cost; } cout << min_cost << endl; return 0; }这篇关于昂贵的聘礼 （dfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
