Home PAT 1106 Lowest Price in Supply Chain
Post
Cancel

PAT 1106 Lowest Price in Supply Chain

Link

用 DFS 可以 AC, 但是通过记录父节点然后从各个 retailer (叶子节点) 向 root (根节点) 回溯, 测试点 6 就会 TLE.

(两种代码都记录一下, 有时间了再分析时间复杂度…)

AC 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int n,minv=0x3f3f3f3f,num;
double p,r,ans;
vector<int>members[100010];
void DFS(int root,int depth){
    if(members[root].size()==0){
        if(depth<minv){
            minv=depth;
            num=1;
        }else if(depth==minv) num++;
        return;
    }
    for(int i=0;i<members[root].size();++i)
        DFS(members[root][i],depth+1);
}
int main() {
    scanf("%d%lf%lf",&n,&p,&r);
    r/=100.0;
    for(int i=0;i<n;++i){
        int k,id;
        scanf("%d",&k);
        for(int j=0;j<k;++j){
            scanf("%d",&id);
            members[i].push_back(id);
        }
    }
    DFS(0,0);
    ans=p*pow(r+1.0,minv);
    printf("%.4lf %d\n",ans,num);
    return 0;
}

测试点 6 TLE 的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
int n,minv=0x3f3f3f3f,num;
double p,r,ans;
int father[100010];
vector<int>retailers;
int toRoot(int x){
    int len=0;
    while(x){
        x=father[x];
        len++;
    }
    return len;
}
int main() {
    scanf("%d%lf%lf",&n,&p,&r);
    r/=100.0;
    for(int i=0;i<n;++i){
        int k,id;
        scanf("%d",&k);
        if(k==0) retailers.push_back(i);
        for(int j=0;j<k;++j){
            scanf("%d",&id);
            father[id]=i;
        }
    }
    for(int i=0;i<retailers.size();++i){
        int len=toRoot(retailers[i]);
        if(len<minv){
            minv=len;
            num=1;
        }else if(len==minv) num++;
    }
    ans=p*pow(r+1.0,minv);
    printf("%.4lf %d\n",ans,num);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.