本文主要是介绍HDU 2677 Dota all stars 深搜，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有商店，商店里面有装备的名字和价格，一个人要买装备，他本身自己也有一些装备，给出已有装备名和个数，然后告诉你合成公式，最后要求合成若干个数的装备总共花多少钱。所有装备一定可以合成出来。
想法：用字符串处理为每一个装备编号，然后设定结构体，设置相应的names，price，number变量。然后建图反向见图，从大装备往小装备搜索。
#include<iostream>
#include<cstring>
#include<queue>
#define inf 0x7fffffff
using namespace std;
int a,b,c,d,cnt;
struct node
{string names;int num;double price;
}equ[10000];
struct nodee
{int v,next;
}e[20000];
int head[10000],ct;
void init()
{memset(head,-1,sizeof(head));ct=0;
}
void add(int a,int b)
{e[ct].v=b;e[ct].next=head[a];head[a]=ct++;
}
int Find(string x)
{for(int i=0;i<cnt;i++){if(equ[i].names==x) return i;}equ[cnt].names=x;equ[cnt].num=0;equ[cnt++].price=inf;return cnt-1;
}
int dfs(int id,int num)
{if(equ[id].num>=num){equ[id].num-=num;return 0;}else { num-=equ[id].num;equ[id].num=0;if(equ[id].price!=inf){return num*equ[id].price;}else{int res=0;for(int i=head[id];i+1;i=e[i].next){int v=e[i].v;res+=dfs(v,num);}return res;}}
}
int main()
{while(cin>>a){cnt=0;init();queue<int>q;while(!q.empty()) q.pop();for(int i=1;i<=a;i++){string k;int n,mark=0;cin>>k>>n;for(int j=0;j<cnt;j++){if(k==equ[j].names){mark=1;break;}}if(!mark){equ[cnt].names=k;equ[cnt].num=0;equ[cnt++].price=n;}}cin>>b;for(int i=1;i<=b;i++){string k;int n;cin>>k>>n;int pos=-1;for(int j=0;j<cnt;j++){if(k==equ[j].names){pos=j;break;}}if(pos!=-1){equ[pos].num+=n;}else{equ[cnt].names=k;equ[cnt].num=n;equ[cnt++].price=inf;}}cin>>c;for(int i=1;i<=c;i++){string k;cin>>k;q.push(Find(k));cin>>k;while(k!="="){cin>>k;q.push(Find(k));cin>>k;}cin>>k;int u=Find(k);while(!q.empty()){int v=q.front();q.pop();add(u,v);}}cin>>d;int res=0;for(int i=1;i<=d;i++){string k;int n;cin>>k>>n;res+=dfs(Find(k),n);}cout<<res<<endl;}return 0;
} 这篇关于HDU 2677 Dota all stars 深搜的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
