BZOJ2438: [中山市选2011]杀人游戏-布布扣-bubuko.com

BZOJ2438: [中山市选2011]杀人游戏

Description

一位冷血的杀手潜入 Na-wiat，并假装成平民。

警察希望能在 N 个人里面，查出谁是杀手。

警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。

假如查证的对象是杀手，杀手将会把警察干掉。

现在警察掌握了每一个人认识谁。

每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。

问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？

Input

第一行有两个整数 N,M。
接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x,例如19260817等等。。。）。

Output

仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。

Sample Input

5 4
1 2
1 3
1 4
1 5

Sample Output

0.800000

HINT

警察只需要查证 1。

假如1是杀手，警察就会被杀。

假如 1不是杀手，他会告诉警察 2,3,4,5 谁是杀手。

而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概率是0.8。

对于 100%的数据有 1≤N ≤ 10 0000,0≤M ≤ 30 0000

数据已加强！

题解Here!

首先$Tarjan$缩点没得的说。

因为缩点之后我们只需要查询环中的一个人就可以知道整个环的信息。

而且若一个环又指向另一个环，那么我们要是选择一个缩点后入度为$0$的点，即可以把其连通的若干个环的信息全部了解。

这个很好理解。

但是这样还有还有一些错误：

煮个栗子：

若一共有$N$个人，我们查询了一些人，使得我们知道了$N-1$个人的身份（都是平民，否则你就挂了），那么剩下的一个人一定是杀手（排除法）。

那么我们就可以少去查询一个人。

所以，我们要去寻找一个大小为$1$且入度为$0$的点（就是缩点后一个与世隔绝的人），并且他指向的点入度不为$1$（就是能只通过这个人来获取信息），那么我们就可以少一次询问。

我们对此打一个标记：

能少一次询问，$flag=1$；

否则，$flag=0$。

最终答案就是：

$$1-\frac{\text{缩点后入度为0的点-flag}}{n}$$

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 100010
using namespace std;
int n,m,c=1,ans=0;
int head[MAXN],colour[MAXN],num[MAXN],indegree[MAXN];
struct Edge{
	int x,y;
}edge[MAXN*3];
struct Graph{
	int next,to;
}a[MAXN*3];
inline int read(){
	int date=0,w=1;char c=0;
	while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
	while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
	return date*w;
}
namespace Tarjan{
	int d=1,top=1,s=0;
	int cstack[MAXN],deep[MAXN],low[MAXN];
	bool vis[MAXN];
	inline void add(int x,int y){
		a[c].to=y;a[c].next=head[x];head[x]=c++;
	}
	void dfs(int x){
		deep[x]=low[x]=d++;
		vis[x]=true;
		cstack[top++]=x;
		for(int i=head[x];i;i=a[i].next){
			int v=a[i].to;
			if(!deep[v]){
				dfs(v);
				low[x]=min(low[x],low[v]);
			}
			else if(vis[v])low[x]=min(low[x],deep[v]);
		}
		if(low[x]==deep[x]){
			s++;
			do{
				colour[cstack[top-1]]=s;
				vis[cstack[top-1]]=false;
			}while(cstack[--top]!=x);
		}
	}
	void clean(){
		c=1;
		memset(head,0,sizeof(head));
		memset(a,0,sizeof(a));
	}
	void solve(){
		int x,y;
		for(int i=1;i<=m;i++){
			edge[i].x=read();edge[i].y=read();
			add(edge[i].x,edge[i].y);
		}
		for(int i=1;i<=n;i++)if(!deep[i])dfs(i);
		for(int i=1;i<=n;i++)num[colour[i]]++;
		clean();
		for(int i=1;i<=m;i++){
			x=edge[i].x;y=edge[i].y;
			if(colour[x]!=colour[y]){
				indegree[colour[y]]++;
				add(colour[x],colour[y]);
			}
		}
	}
}
void work(){
	bool flag=false;
	for(int i=1;i<=Tarjan::s;i++){
		if(!flag&&!indegree[i]&&num[i]==1){
			bool f=false;
			for(int j=head[i];j;j=a[j].next){
				int v=a[j].to;
				if(indegree[v]==1)f=true;
			}
			if(!f)flag=true;
		}
		if(!indegree[i])ans++;
	}
	if(flag)ans--;
	printf("%.6lf\n",1.00-1.00*ans/n);
}
void init(){
	n=read();m=read();
	Tarjan::solve();
}
int main(){
	init();
	work();
	return 0;
}

BZOJ2438: [中山市选2011]杀人游戏

原文：https://www.cnblogs.com/Yangrui-Blog/p/9924528.html