ICPC Asia Shenyang 2019 Dudu's maze
- 2019 年 10 月 4 日
- 笔记
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_41603898/article/details/100893774
这两次被dfs上了两课。
hhh
题意： 一个迷宫有n个房间，m条路，房间除了糖果就是怪物。小明从1号房间出发，他足够聪明且知道地图，遇到怪物必须使用
传送门，传送门会将你传送到和当前房间连接的任意一间（每边等概率，有重边）。不过传送门只能使用一次。问最大的糖果期望。
解：dfs
#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 1e5+5; vector<int> to[maxn]; int pos[maxn],fa[maxn]; bool vis[maxn]; bool book[maxn]; int n,m,k; int cnt; double ans,mx,num; void init() { for(int i=0;i<=n;i++){ to[i].clear(); vis[i] = false; book[i] = false; fa[i] = 0; } } void dfs1(int u){ book[u] = 1; if(vis[u]){ pos[++cnt] = u; return ; } ans++; for(int i=0;i<to[u].size();i++){ int nx = to[u][i]; if(book[nx])continue; dfs1(nx); } } void dfs2(int u,int pos){ if(book[u] || vis[u]) return; fa[u] = pos; num++; for(int i=0;i<to[u].size();i++){ int nx = to[u][i]; if(fa[nx]==pos)continue; dfs2(nx,pos); } } int main() { int _; scanf("%d",&_); while(_--){ init(); scanf("%d %d %d",&n,&m,&k); for(int i=1;i<=m;i++){ int u,v; scanf("%d %d",&u,&v); to[u].push_back(v); to[v].push_back(u); } ans = 0; cnt = 0; mx = 0; for(int i=1;i<=k;i++){ int tp; scanf("%d",&tp); vis[tp] = true; } dfs1(1); int v=0; for(int i=1;i<=cnt;i++){ num =0; for(int j=0;j<to[pos[i]].size();j++){ dfs2(to[pos[i]][j],++v); } mx = max(mx,num/to[pos[i]].size()); } printf("%.6lfn",ans+mx); } return 0; }
