LG4819/BZOJ2438 「中山市选2011」杀人游戏 Tarjan缩点+概率

问题描述

LG4819

BZOJ2438

题解

发现如果有一些人之间认识关系形成环，只需要问一个人就能把控整个环。

\(\mathrm{Tarjan}\)缩点。

缩点之后所有入度为\(0\)的点，必须询问。

注意特判有没有孤身一人的。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-'){

		fh=-1;ch=getchar();

	}

	else fh=1;

	while(ch>='0'&&ch<='9'){

		x=(x<<1)+(x<<3)+ch-'0';

		ch=getchar();

	}

	x*=fh;

}

const int maxn=200000+7;

const int maxm=600000+7;

int Head[maxn],to[maxm],Next[maxm],tot,u[maxm];

int n,m,cnt,sta[maxn],top;

int bel[maxn],dfn[maxn],low[maxn],ind;

int size[maxn],flag;

bool vis[maxn];

void add(int x,int y){

	to[++tot]=y,Next[tot]=Head[x],Head[x]=tot,u[tot]=x;

}

void tarjan(int x){

	low[x]=dfn[x]=++ind;vis[x]=1;sta[++top]=x;

	for(int i=Head[x];i;i=Next[i]){

		int y=to[i];

		if(dfn[y]){

			if(vis[y]) low[x]=min(low[x],dfn[y]);

		}

		else{

			tarjan(y);

			low[x]=min(low[x],low[y]);

		}

	}

	if(dfn[x]==low[x]){

		++cnt;

		while(sta[top]!=x){

			bel[sta[top]]=cnt,vis[sta[top]]=0,top--;size[cnt]++;

		}

		bel[sta[top]]=cnt,vis[sta[top]]=0,top--;size[cnt]++;

	}

}

double ans;

int rd[maxn];

int cot;

int main(){

	read(n);read(m);cnt=n;

	for(int x,y,i=1;i<=m;i++){

		read(x);read(y);add(x,y);//add(y,x);

	}

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

		if(dfn[i]) continue;

		tarjan(i);

	}

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

		int x=bel[u[i]],y=bel[to[i]];

		if(x==y) continue;

		++rd[y];add(x,y);

	}

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

		if(!rd[i]) ++cot;

		if(!flag&&!rd[i]&&size[i]==1){

			int ok=0;

			for(int j=Head[i];j;j=Next[j]){

				int y=to[j];

				if(rd[y]==1) ok=1;

			}

			if(!ok) flag=1;

		}

	}

//	cout<<flag<<endl<<cot<<endl<<cnt<<endl;

	if(flag) --cot;

	ans=1.0-(double)(cot)/(double)n*1.0;

	cout<<fixed<<setprecision(6)<<ans<<endl;

	return 0;

}

巴特西

LG4819/BZOJ2438 「中山市选2011」杀人游戏 Tarjan缩点+概率

问题描述

题解

最新文章

热门文章