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

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

Input

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

Output

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

Sample Input5 4
1 2
1 3
1 4
1 5

Sample Output0.800000

HINT

警察只需要查证 1。假如1是杀手，警察就会被杀。假如 1不是杀手，他会告诉警

察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概

率是0.8。

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

Source

有向图的Tarjen缩点。。。到点为止。。。

详情看代码。。。由于是有向图，可能有返非祖边（到其它子树），要注意特判、、、

#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<functional>#include<iostream>#include<cmath>#include<cctype>#include<ctime>using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Fork(i,k,n) for(int i=k;i<=n;i++)#define Rep(i,n) for(int i=0;i<n;i++)#define ForD(i,n) for(int i=n;i;i--)#define RepD(i,n) for(int i=n;i>=0;i--)#define Forp(x) for(int p=pre[x];p;p=next[p])#define Lson (x<<1)#define Rson ((x<<1)+1)#define MEM(a) memset(a,0,sizeof(a));#define MEMI(a) memset(a,127,sizeof(a));#define MEMi(a) memset(a,128,sizeof(a));#define INF (2139062143)#define F (100000007)#define MAXN (600000+10)#define MAXM (600000+10)long long mul(long long a,long long b){return (a*b)%F;}long long add(long long a,long long b){return (a+b)%F;}long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}typedef long long ll;int n,m,edge[MAXM],next[MAXM]={0},pre[MAXN]={0},size=0;void addedge(int u,int v){edge[++size]=v;next[size]=pre[u];pre[u]=size;}//void addedge2(int u,int v){addedge(u,v),addedge(v,u); }bool b[MAXN]={0};int dfs[MAXN],dis[MAXN]={0},s[MAXN]={0},tot=0,numk[MAXN]={0},h[MAXN]={0},kind=0,tim=0;void tar(int x,int fa){dis[x]=dfs[x]=++tim;b[x]=1;s[++tot]=x;Forp(x){int v=edge[p];if (!b[v]) tar(v,x),dfs[x]=min(dfs[x],dfs[v]);else if (!h[v]) dfs[x]=min(dfs[x],dis[v]); }if (dfs[x]==dis[x]){++kind;while (tot){numk[h[s[tot]]=kind]++; if (s[tot--]==x) break;}}}int indegree[MAXN]={0};int main(){//freopen("bzoj2438.in","r",stdin);//freopen(".out","w",stdout);scanf("%d%d",&n,&m);For(i,m){int u,v;scanf("%d%d",&u,&v);addedge(u,v);}For(i,n) if (!b[i]) tar(i,0);For(x,n)Forp(x){int v=edge[p];if (h[x]^h[v]) indegree[h[v]]++;}int ans=0,s1=0; //s1表示分量内大小为1的单独块 For(i,kind) if (!indegree[i]) {ans++;if (numk[i]==1) s1=1;}if (ans>1) ans-=s1;printf("%.6lf\n",1.000000-(double)ans/n); //For(i,kind) cout<<numk[i]<<' ';return 0;}