DFS-深度优先搜索

DFS-深度优先搜索

样题1-全排列

题目描述：

输入一个数n，输出n的全排列

程序源代码：

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
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100];
int book[100];
void dfs(int step)
{
    int i;
    if(step==n+1)  //这里表示dfs结束,没有可以排的数字了
    {
        for (i = 1;  i<=n ; i++) {
            cout<<a[i]<<" ";
        }
        cout<<endl;
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(book[i]==0)  //说明数字i还没有被使用,可以用来排列
        {
            a[step]=i;//排列数字i
            book[i]=1;//标记数字i为已使用
            dfs(step+1);
            //继续排列没有使用的数字
            book[i]=0;
            //这里表示dfs调用结束了,意思是数字i已经全部排列完了，但还需要
            //按照顺序将数字i收回，重新排列。
        }
    }
    return;
}
int main() {
    cin>>n;
    dfs(1); //dfs函数的开始
    return 0;
}

程序输入：

1
3

程序输出：

1
2
3
4
5
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

样题二-自然数的拆分问题

题目描述：

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。现在给你一个自然数n，要求你求出n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

程序源代码：

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
#include <bits/stdc++.h>
using namespace std;
int num;
int a[100000]={1};
void dfs(int n,int t)
{
    if(n==0)
    {
        for(int i=1;i<=t-1;i++)//输出一种拆分方案

            if(i!=t-1) cout<<a[i]<<"+";
            else cout<<a[i];
        cout<<endl;
        return ;
    }
    for (int i=a[t-1];i<=n;i++) {
        if(i<num)//当前数i要大于等于前一位数，且不超过n
        {
            a[t]=i;//保存当前拆分的数i
            n-=i;//n减去数i，n的值将继续拆分
            dfs(n,t+1);
            n+=i;//回溯：加上拆分的数，以便产生所有可能的拆分
        }
    }
    return ;

}
int main()
{
    cin>>num;
    dfs(num,1);
    return 0;
}

程序输入：

1
7

程序输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

样例三：L2-038 病毒溯源 (25 分)

题目描述：

病毒容易发生变异。某种病毒可以通过突变产生若干变异的毒株，而这些变异的病毒又可能被诱发突变产生第二代变异，如此继续不断变化。

现给定一些病毒之间的变异关系，要求你找出其中最长的一条变异链。

在此假设给出的变异都是由突变引起的，不考虑复杂的基因重组变异问题 —— 即每一种病毒都是由唯一的一种病毒突变而来，并且不存在循环变异的情况。

输入格式：

输入在第一行中给出一个正整数 N（≤104），即病毒种类的总数。于是我们将所有病毒从 0 到 N−1 进行编号。

随后 N 行，每行按以下格式描述一种病毒的变异情况：

1
k 变异株1 …… 变异株k

其中 k 是该病毒产生的变异毒株的种类数，后面跟着每种变异株的编号。第 i 行对应编号为 i 的病毒（0≤i<N）。题目保证病毒源头有且仅有一个。

输出格式：

首先输出从源头开始最长变异链的长度。

在第二行中输出从源头开始最长的一条变异链，编号间以 1 个空格分隔，行首尾不得有多余空格。如果最长链不唯一，则输出最小序列。

注：我们称序列 { a1,⋯,a**n } 比序列 { b1,⋯,b**n } “小”，如果存在 1≤k≤n 满足 a**i=b**i 对所有 i<k 成立，且 a**k<b**k。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
10
3 6 4 8
0
0
0
2 5 9
0
1 7
1 2
0
2 3 1结尾无空行

输出样例：

1
2
4
0 4 9 1结尾无空行

程序源代码：

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
vector<int> ans, tmp;
bool a[10005][10005];
bool book[10005];
int maxn;
int n;
void dfs(int root,int len)
{
    if(len>maxn)
    {
        maxn =len;
        ans = tmp;

    }
    else if(len == maxn && tmp < ans)
    {
        ans = tmp;
    }
    for (int i = 0; i <n ; ++i)
    {
        if(a[root][i]) //连通
        {
            tmp.push_back(i);
            dfs(i,len+1);
            tmp.pop_back();
        }
    }
    return ;
}
int main() {

    cin>>n;
    int root=0;
    for (int i = 0; i <n ; ++i) {
        int k;
        cin>>k;
        for (int j = 0; j <k ; ++j) {
            int x;
            cin>>x;
            book[x]=true;    //用来判断谁是病毒源头，题目给出病毒源头有且仅有一个
            a[i][x]=true;    //使用邻接矩阵来储存图，连通为true，否则为false
        }
    }
    while(book[root]) root++;  //寻找病毒源头
    tmp.push_back(root);
    dfs(root,1); //从病毒源头开始dfs
    cout<<ans.size()<<endl;
    //输出格式控制
    for(int i=0; i < ans.size(); i++){
       if(i!=ans.size()-1)
       {
           cout<<ans[i]<<" ";
       }
       else
       {
           cout<<ans[i];
       }
        
    }
    return 0;
}

样题四：L2-020 功夫传人 (25 分)

题目描述：

一门武功能否传承久远并被发扬光大，是要看缘分的。一般来说，师傅传授给徒弟的武功总要打个折扣，于是越往后传，弟子们的功夫就越弱…… 直到某一支的某一代突然出现一个天分特别高的弟子（或者是吃到了灵丹、挖到了特别的秘笈），会将功夫的威力一下子放大N倍 —— 我们称这种弟子为“得道者”。

这里我们来考察某一位祖师爷门下的徒子徒孙家谱：假设家谱中的每个人只有1位师傅（除了祖师爷没有师傅）；每位师傅可以带很多徒弟；并且假设辈分严格有序，即祖师爷这门武功的每个第i代传人只能在第i-1代传人中拜1个师傅。我们假设已知祖师爷的功力值为Z，每向下传承一代，就会减弱r%，除非某一代弟子得道。现给出师门谱系关系，要求你算出所有得道者的功力总值。

输入格式：

输入在第一行给出3个正整数，分别是：N（≤105）——整个师门的总人数（于是每个人从0到N−1编号，祖师爷的编号为0）；Z——祖师爷的功力值（不一定是整数，但起码是正数）；r ——每传一代功夫所打的折扣百分比值（不超过100的正数）。接下来有N行，第i行（i=0,⋯,N−1）描述编号为i的人所传的徒弟，格式为：

K**i ID[1] ID[2] ⋯ ID[K**i]

其中K**i是徒弟的个数，后面跟的是各位徒弟的编号，数字间以空格间隔。K**i为零表示这是一位得道者，这时后面跟的一个数字表示其武功被放大的倍数。

输出格式：

在一行中输出所有得道者的功力总值，只保留其整数部分。题目保证输入和正确的输出都不超过1010。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
10 18.0 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3结尾无空行

输出样例：

1
2
404
结尾无空行

程序源代码：

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
45
46
#include<bits/stdc++.h>
using namespace std;
vector<int> tree[100000];  //用于邻接表建树
int book[100000];
double sum;
double r;
void dfs(int index,double power)
{
    if(book[index]) //是得道者就乘他的倍数 
    {
        sum += power * book[index];
        return ;
    }
    for(int i=0;i<tree[index].size();i++)  //遍历整个树
    {
        dfs(tree[index][i],power*r);
    }
}
int main() {
    int n;
    double z;
    cin>>n>>z>>r;
    r=(100-r)/100.0;
    for(int i=0;i<n;i++)
    {
        int k;
        cin>>k;
        if(k==0)   //这个弟子是否为得道者
        {
            int power;
            cin>>power;
            book[i]=power;   //记录得道者放大倍数
        }
        else{
            for(int j=0;j<k;j++)
            {
                int id;
                cin>>id;
                tree[i].push_back(id);      //使用邻接表建树
            }
        }
    }
    dfs(0,z);
    cout<<(int)sum<<endl;
    return 0;
}

题目相关链接：

[P2404 自然数的拆分问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)]: “ 样例二-自然数的拆分问题”

[题目详情 - L2-038 病毒溯源 (25 分) (pintia.cn)]: “ 样例三-L2-038 病毒溯源 (25 分)”

[题目详情 - L2-020 功夫传人 (25 分) (pintia.cn)]: “ 样例四-L2-020 功夫传人 (25 分)”