K Search for Mafuyu 详解【树（图）的遍历·带权节点】【2021-ACM-ICPC-济南站】

96 阅读 0 评论 64 点赞

我是靠谱客的博主矮小大地，这篇文章主要介绍K Search for Mafuyu 详解【树（图）的遍历·带权节点】【2021-ACM-ICPC-济南站】，现在分享给大家，希望可以做个参考。

刚刚打完11：00-16：00的acm-icpc济南站.这场一言难尽
1题就能铜牌，2题银牌，3题金牌2333
我们过了1题，打铁了呜呜，过的那题是 K Search for Mafuyu
题面如下
在这里插入图片描述

（一）题目大意
题目大意：.S中有n个房间，（n-1）对是连通的，M等概率隐藏在S的各个非1号房间中.现在K从1号房间出发，要找到M，K可以在连通的房间中移动，移动一步耗时一秒。对于每组样例，.输出最小的期望时间.
（二）思路及样例分析
n个房间呈树形结构，根节点是K的出发点即1号房间
既然M可能藏在任意房间（除1号房），那么需遍历整棵树访问每一个节点,
遍历的同时要记录每个节点到达所需的步数
下图4个样例中.，回溯及路径已在图上标出，红色数字为每一个树的节点需要几步遍历.
红色数字求和得到期望总时间，再除以（n-1）得到期望最小时间
且模拟样例可知，遍历顺序与结果无关
在这里插入图片描述

（三）AC代码
队友写的，改了一些时间，最后把邻接表的ne[N],e[N]数组开到ne[2N],e[2N]才对的2333
大致就是邻接表建无向图，dfs遍历每个节点，同时维护每个节点的步数

复制代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <cstring>
//#include <set>
//#include <list>
//#include <unordered_set>
//#include <unordered_map>
//
//#define gcd __gcd
//#define LL long long

using namespace std;

const int N = 100 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;

int h[N],ne[2*N],e[2*N],st[N],w[N];
int idx;
int sum;
int n,d;
int ans;
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void dfs(int num)
{
 	if(sum==n)
 		return;
    
    for(int i=h[num];i!=-1;i=ne[i])
    {
     
        if(!st[e[i]]){
            st[e[i]] = 1;
            sum ++;
            w[e[i]] = d+1;
            d++;
            ans += d;
            dfs(e[i]);
            d++;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d",&n);
        idx = 0,d = 0;
        for(int i=0;i<=n;i++)h[i] = -1,st[i] = 0;
        sum = 0;
        ans = 0;
        for(int i=1;i<n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
   			add(b,a);
   			//无向图加2次
            add(a,b);
        }
        
        st[1] = 1;
        w[1] = 0;
        sum ++;
        dfs(1);
  
//  for(int i=1;i<=n;i++)
//  {
//   cout << w[i] << " ";
//  }
//  cout << endl;
//  for(int i=0;i<idx;i++)cout << e[i] << " ";
//  cout << endl;
        
//        for(int i=1;i<=n;i++)
//        {
//            ans += w[i];
//        }
        // ans = ans / (n-1);
//        cout << ans << endl;
        double res = (double)ans;
        printf("%.10lfn",res/(n-1));
    }
    return 0;
}

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <cstring>
//#include <set>
//#include <list>
//#include <unordered_set>
//#include <unordered_map>
//
//#define gcd __gcd
//#define LL long long

using namespace std;

const int N = 100 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;

int h[N],ne[2*N],e[2*N],st[N],w[N];
int idx;
int sum;
int n,d;
int ans;
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void dfs(int num)
{
 	if(sum==n)
 		return;
    
    for(int i=h[num];i!=-1;i=ne[i])
    {
     
        if(!st[e[i]]){
            st[e[i]] = 1;
            sum ++;
            w[e[i]] = d+1;
            d++;
            ans += d;
            dfs(e[i]);
            d++;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    
    int tt;
    scanf("%d",&tt);
    while(tt--)
    {
        scanf("%d",&n);
        idx = 0,d = 0;
        for(int i=0;i<=n;i++)h[i] = -1,st[i] = 0;
        sum = 0;
        ans = 0;
        for(int i=1;i<n;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
   			add(b,a);
   			//无向图加2次
            add(a,b);
        }
        
        st[1] = 1;
        w[1] = 0;
        sum ++;
        dfs(1);
  
//  for(int i=1;i<=n;i++)
//  {
//   cout << w[i] << " ";
//  }
//  cout << endl;
//  for(int i=0;i<idx;i++)cout << e[i] << " ";
//  cout << endl;
        
//        for(int i=1;i<=n;i++)
//        {
//            ans += w[i];
//        }
        // ans = ans / (n-1);
//        cout << ans << endl;
        double res = (double)ans;
        printf("%.10lfn",res/(n-1));
    }
    return 0;
}