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

昂贵的聘礼

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 20000/10000K (Java/Other)

Total Submission(s) : 68   Accepted Submission(s) : 21

1 410000 3 22 80003 50001000 2 14 2003000 2 14 20050 2 0

5250

中文题，不解释。

思路：

用的dfs，看很多人都是用的图论的知识做的，有点懵。。。图论掌握的还是不扎实。。。下面附上dfs的代码吧：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       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<
       
        <
       
      
     
    
   

枚举等级限制。以下转载

对于从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 
   
      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;  }
   

转载地址：https://blog.csdn.net/sinat_37668729/article/details/76934054 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！