专栏首页wymICPC Asia Shenyang 2019 Dudu's maze

ICPC Asia Shenyang 2019 Dudu's maze

版权声明:本文为博主原创文章,遵循 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("%.6lf\n",ans+mx);
	}
	return 0;
 } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768
  • [LightOJ-1356] Prime Independence 二分图+素数分解

    数据大,需要用优化的二分图,对每个数求出素因数,不独立的两个数之间就差一个素因数,若 a 去掉这个素因数得到b

    用户2965768
  • 区间更新与点值

    用户2965768
  • 有序数组中与任意数组查找不同的部分-二分查找

    sr
  • 常见指针定义解读

    最近做的C/C++技术面试比较多,发现了一些共同的问题,对于如下所示的指针认识,多数面试者都答错了,作为过来人,这种情况还可以理解的,放在一起确实有些复杂。 ...

    一见
  • leetcode题解 | 78. 子集

    这个题目很容易想到使用DFS的方式来解决,因为组合的题容易产生转移方程,这样也是没有什么问题的。

    ACM算法日常
  • 你必须知道的指针基础-7.void指针与函数指针

      void *表示一个“不知道类型”的指针,也就不知道从这个指针地址开始多少字节为一个数据。和用int表示指针异曲同工,只是更明确是“指针”。

    Edison Zhou
  • Android Heroes Reading Notes 2

    《Android群英传》读书笔记 (2) 第三章 控件架构与自定义控件详解 + 第四章 ListView使用技巧 + 第五章 Scroll分析

    宅男潇涧
  • 洛谷P2763 试题库问题(最大流)

    attack
  • 洛谷P3254 圆桌问题(最大流)

    attack

扫码关注云+社区

领取腾讯云代金券