bzoj 2438: [中山市选2011]杀人游戏【tarjan】

没看太懂题意orz

最优的是tarjan缩点之后问入度为0的点，因为问这个点可以知道整个块的情况

答案是这ans个入度为0的点都不是杀手的概率\( \frac{n-ans}{n} \)

但是有特殊情况就是size为1的单独scc，这是ans--，因为其他点确定之后这个点就确定了

#include<iostream>

#include<cstdio>

using namespace std;

const int N=300005;

int n,m,h[N],cnt,dfn[N],low[N],tot,si[N],bl[N],col,s[N],top,ans,d[N],rl[N];

bool v[N];

struct qwe

{

	int ne,no,to;

}e[N];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].no=u;

	e[cnt].to=v;

	h[u]=cnt;

}

void tarjan(int u)

{

	low[u]=dfn[u]=++tot;

	v[s[++top]=u]=1;

	for(int i=h[u];i;i=e[i].ne)

	{

		if(!dfn[e[i].to])

		{

			tarjan(e[i].to);

			low[u]=min(low[u],low[e[i].to]);

		}

		else if(v[e[i].to])

			low[u]=min(low[u],dfn[e[i].to]);

	}

	if(dfn[u]==low[u])

	{

		rl[++col]=u;

		while(s[top]!=u)

		{

			bl[s[top]]=col;

			si[col]++;

			v[s[top--]]=0;

		}

		bl[s[top]]=col;

		si[col]++;

		v[s[top--]]=0;

	}

}

int ok(int u)

{

	for(int i=h[rl[u]];i;i=e[i].ne)

		if(d[bl[e[i].to]]==1)

			return 0;

	return 1;

}

int main()

{

	n=read(),m=read();

	for(int i=1;i<=m;i++)

	{

		int x=read(),y=read();

		add(x,y);

	}

	for(int i=1;i<=n;i++)

		if(!dfn[i])

			tarjan(i);

	for(int i=1;i<=m;i++)

		if(bl[e[i].no]!=bl[e[i].to])

			d[bl[e[i].to]]++;

	for(int i=1;i<=col;i++)

		if(!d[i])

			ans++;//cerr<<ans<<endl;

	for(int i=1;i<=col;i++)

		if(si[i]==1&&!d[i]&&ok(i))

		{

			ans--;

			break;

		}

	printf("%.6f\n",(double)(n-ans)/n);

	return 0;

}

巴特西

bzoj 2438: [中山市选2011]杀人游戏【tarjan】

最新文章

热门文章