GYM101635E Ingredients

题目链接：https://vjudge.net/problem/Gym-101635E

题目大意：

　　给定一个有 \(N\) 条边的有向无环图（有多个起点），每条边都有其费用和收益，现要从一个或多个起点出发，以某一个或多个点为终点（一个点不能多次作为终点；如果有多个方案能到达同一个点，则选择总费用最少的），问在使得总费用不超过 \(B\) 的大前提下，能得到的最大收益（如果有多个得到最大收益的方法，则选择使得费用最少的）。输出最大收益及其对应的总费用。

　　（建议仔细地读一下 \(Important Notes\)）

知识点：　　DP、最短路

解题思路：

　　先用 \(Dijkstra\) 跑出从各个起点到各个点的最小费用及其对应的收益（如果有多个费用最小的方案，则选择收益最大的那个），再用 \(dp\) 计算出在各个总费用下所能得到的最大收益。

AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 const int maxm = +, maxn = +, inf=0x3f3f3f3f;

 struct Edge{

     int to,nxt,cost,prestige;

 }edge[maxm];

 int head[maxm],tot;

 void init(){

     memset(head,-,sizeof(head));

     tot=;

 }

 void addedge(int u,int v,int cost,int pres){

     edge[tot].to=v;

     edge[tot].nxt=head[u];

     edge[tot].prestige=pres;

     edge[tot].cost=cost;

     head[u]=tot++;

 }

 int min_cost[maxn],max_pres[maxn];

 bool noroot[maxn];

 map<string,int> ind;

 void dijkstra(int s){

     queue<int> que;

     que.push(s);

     min_cost[s]=max_pres[s]=;

     while(!que.empty()){

         int v=que.front();

         que.pop();

         for(int i=head[v];i!=-;i=edge[i].nxt){

             int to=edge[i].to;

             if(min_cost[to]>min_cost[v]+edge[i].cost){

                 min_cost[to]=min_cost[v]+edge[i].cost;

                 max_pres[to]=max_pres[v]+edge[i].prestige;

                 que.push(to);

             }

             else if(min_cost[to]==min_cost[v]+edge[i].cost&&max_pres[to]<max_pres[v]+edge[i].prestige){

                 max_pres[to]=max_pres[v]+edge[i].prestige;

                 que.push(to);

             }

         }

     }

 }

 int dp[maxn];

 int main(){

     std::ios::sync_with_stdio(false);   //如果没有加速输入输出的话会T

     int B,N,cos,pre,u,v;

     int cnt=;

     string to,from,tmp;

     cin>>B>>N;

     init();

     for(int i=;i<N;i++){

         cin>>to>>from>>tmp>>cos>>pre;

         if(!ind[to])

             ind[to]=cnt++;

         v=ind[to];

         if(!ind[from])

             ind[from]=cnt++;

         u=ind[from];

         addedge(u,v,cos,pre);

         noroot[v]=true;

     }

     for(int i=;i<cnt;i++)

         min_cost[i]=inf,max_pres[i]=;

     for(int i=;i<cnt;i++){

         if(!noroot[i])

             dijkstra(i);

     }

     dp[]=;

     for(int i=;i<cnt;i++){

         for(int j=B;j>=min_cost[i];j--)

             dp[j]=max(dp[j],dp[j-min_cost[i]]+max_pres[i]);

     }

     int ans1=,ans2=;

     for(int i=;i<=B;i++){

         if(dp[i]>ans1)

             ans1=dp[i],ans2=i;

     }

     cout<<ans1<<endl;

     cout<<ans2<<endl;

     return ;

 }

巴特西

GYM101635E Ingredients

最新文章

热门文章