首页 > 代码库 > 【BZOJ2438】[中山市选2011]杀人游戏 Tarjan

【BZOJ2438】[中山市选2011]杀人游戏 Tarjan

2024-10-05 22:46:39   218人阅读

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

Description

一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，查出谁是杀手。 警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人， 谁是杀手， 谁是平民。 假如查证的对象是杀手， 杀手将会把警察干掉。 现在警察掌握了每一个人认识谁。 每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。 
问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？

Input

第一行有两个整数 N,M。 
接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x,例如胡*锦*涛同志） 。

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

题解：结论：ans=1-(最少查证的人数/总人数)

我们先跑Tarjan缩点，然后每个入度为0的强联通分量我们都至少查证其中的一个人，其余的都没有必要查证，所以最少查证的人数就是入度为0的强联通分量的个数。

咦？哪里不对？

如果只有2个人，他们互相不认识，那么我们只需要查证一个人就能直接知道另一个人的身份。所以如果存在某个入度为0，大小为1，且指向的其他强联通分量入度都>1时，答案--。

 

#include <cstdio>#include <iostream>#include <cstring>#include <vector>using namespace std;const int maxn=100010,maxm=300010;int n,m,cnt,tot,top,ans,sum;int to[maxm],next[maxm],head[maxn],dep[maxn],low[maxn],ins[maxn],sta[maxn],d[maxn],bel[maxn],vis[maxn];vector<int> v[maxn];void add(int a,int b){	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;}int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}void tarjan(int x){	dep[x]=low[x]=++tot,ins[x]=1,sta[++top]=x;	for(int i=head[x];i!=-1;i=next[i])	{		if(!dep[to[i]])	tarjan(to[i]),low[x]=min(low[x],low[to[i]]);		else if(ins[to[i]])	low[x]=min(low[x],dep[to[i]]);	}	if(dep[x]==low[x])	{		sum++;		int t;		do		{			t=sta[top--],v[sum].push_back(t),bel[t]=sum,ins[t]=0;		}while(t!=x);	}}bool islast(int x){	int i,j,flag=0;	for(i=0;i<v[x].size();i++)		for(j=head[v[x][i]];j!=-1;j=next[j])			if(d[bel[to[j]]]==1)	return 0;	return 1;}int main(){	n=rd(),m=rd();	int i,j,k,a,b;	memset(head,-1,sizeof(head));	for(i=1;i<=m;i++)	a=rd(),b=rd(),add(a,b);	for(i=1;i<=n;i++)	if(!dep[i])	tarjan(i);	for(i=1;i<=sum;i++)		for(j=0;j<v[i].size();j++)			for(k=head[v[i][j]];k!=-1;k=next[k])				if(bel[to[k]]!=i&&vis[bel[to[k]]]!=i)					vis[bel[to[k]]]=i,d[bel[to[k]]]++;	for(i=1;i<=sum;i++)	if(!d[i])	ans++;	for(i=1;i<=sum;i++)	{		if(!d[i]&&v[i].size()==1&&islast(i))		{			ans--;			break;		}	}	printf("%.6lf",(1.0*n-ans)/n);	return 0;}

 

【BZOJ2438】[中山市选2011]杀人游戏 Tarjan


联系
我们