B1079 Total Sales of Supply Chain (BFS,DFS)

B1079 Total Sales of Supply Chain (25分)

//第一处bug在price*（1+rate/100）,没看懂题意。
//第二处bug在递归边界处使用price，多加了一次price

price+=(cost[root]*sum);

DFS

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define lowbit(i)((i)&(-i))
using namespace std;
typedef long long ll;
const int MAX=1e5+20;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
const int SQR=632;//633块，632个
vector<double>vt[MAX];
double price,rate;
double ans=0;
double cost[MAX],book[MAX];
int n;
void dfs(int root,double sum)
{
    if(cost[root]!=0)
    {
        ans+=(cost[root]*sum);
        return ;
    }
    for(int i=0;i<vt[root].size();i++)
        dfs(vt[root][i],sum*rate);
}
int main()
{
    scanf("%d%lf%lf",&n,&price,&rate);
    rate=(rate+100)/100;
    for(int i=0;i<n;i++)
    {
        int k;
        double x;
        scanf("%d",&k);
        if(k)
        {
            for(int j=0;j<k;j++)
            {
                scanf("%lf",&x);
                vt[i].push_back(x);
            }
        }
        else
        {
            scanf("%lf",&x);
            cost[i]=x;
        }
    }
    dfs(0,price);
    printf("%.1f\n",ans);
    return 0;
}

BFS

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#define lowbit(i)((i)&(-i))
using namespace std;
typedef long long ll;
const int MAX=1e5+20;
const int INF=0x3f3f3f3f;
const int MOD=1000000007;
const int SQR=632;//633块，632个
vector<double>vt[MAX];
double price,rate;
double ans=0;
double cost[MAX],r[MAX];
int n;
void bfs(int root)
{
    queue<int>q;
    r[root]=price;
    q.push(root);
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        if(cost[top]!=0)
            ans+=(cost[top]*r[top]);
        for(int i=0;i<vt[top].size();i++)
        {
            int j=vt[top][i];
            r[j]=r[top]*(1+rate);
            q.push(j);
        }
    }
}
int main()
{
    scanf("%d%lf%lf",&n,&price,&rate);
    rate=rate/100;
    for(int i=0;i<n;i++)
    {
        int k;
        double x;
        scanf("%d",&k);
        if(k)
        {
            for(int j=0;j<k;j++)
            {
                scanf("%lf",&x);
                vt[i].push_back(x);
            }
        }
        else
        {
            scanf("%lf",&x);
            cost[i]=x;
        }
    }
    bfs(0);
    printf("%.1f\n",ans);
    return 0;
}