BZOJ2438 杀人游戏

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

说明：警察只需要查证 1。假如1是杀手，警察就会被杀。假如 1不是杀手，他会告诉警察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概率是0.8。

Hint

【数据规模与约定】
对于 100%的数据有 1≤N ≤ 100000, 0≤M ≤ 300000

深刻让我认识到了什么叫面向数据编程。各种小细节。。。

做法：tarjan之后，统计入度为0的点即可（可以从他开始推到其他人）

ps：各种恶心小细节

1、孤点（这个还好）

2、只用询问一个

3、x->y，y->x的小环要算一个

判断部分写的有点冗杂，心态小崩。。。

#include<bits/stdc++.h>
using namespace std;
#define Inc(i,L,r) for(register int i=(L);i<=(r);++i)
const int N = 1e5+10;
struct Edge{
	int cnt,h[N],to[N*3],next[N*3];
	inline void add(int x,int y){
		next[++cnt]=h[x];
		to[cnt]=y;
		h[x]=cnt;
	}
}e;
int n,m;
inline void init(){
	scanf("%d%d",&n,&m);
	Inc(i,1,m){
		int x,y;scanf("%d%d",&x,&y);
		e.add(x,y);
	}
}
int top,s[N],siz[N];
int cnt,tj[N],ll[N];
bool instk[N];
int scc,bl[N];
vector<int>vec[N];
inline void Tarjan(int x){
	tj[x]=ll[x]=++cnt;
	instk[s[++top]=x]=1;
	for(int p=e.h[x];p;p=e.next[p]){
		if(!tj[e.to[p]]){
			Tarjan(e.to[p]);
			ll[x]=min(ll[x],ll[e.to[p]]);
		}else if(instk[e.to[p]])ll[x]=min(ll[x],tj[e.to[p]]);
	}
	if(ll[x]==tj[x]){
		++scc;int v;
		do{
			++siz[scc];
			instk[v=s[top--]]=0;
			vec[bl[v]=scc].push_back(v);
		}while(v^x);
	}
}
int rd[N],cd[N];
inline void solv(){
	int cnt=0;bool flag=0;
	Inc(i,1,scc){
		int size=vec[i].size();
		Inc(j,0,size-1){
			int x=vec[i][j];
			for(int p=e.h[x];p;p=e.next[p])
				if(bl[e.to[p]]^bl[x])++cd[bl[x]],++rd[bl[e.to[p]]];
		}
	}
	Inc(i,1,scc){
		int size=vec[i].size();
		Inc(j,0,size-1){
			int x=vec[i][j];
			for(int p=e.h[x];p;p=e.next[p])
				if(bl[e.to[p]]^bl[x])if(cd[bl[x]]==1&&rd[bl[e.to[p]]]>=2)flag=1;
		}
	}
	Inc(i,1,scc)if(!rd[i])++cnt;
	Inc(i,1,scc)if(!rd[i]&&!cd[i]&&siz[i]==1)flag=1;
	printf("%.6lf\n",(n-cnt+flag-0.0)/(n-0.0));
}
int main(){
	init();
	Inc(i,1,n)if(!tj[i])Tarjan(i);
	solv();
	return 0;
}