Description
一位冷血的殺手潛入 Na-wiat，并假裝成平民。警察希望能在 N 個人里面，查出誰是殺手。?
警察能夠對每一個人進行查證，假如查證的對象是平民，他會告訴警察，他認識的人， 誰是殺手， 誰是平民。 假如查證的對象是殺手， 殺手將會把警察干掉。?
現在警察掌握了每一個人認識誰。?
每一個人都有可能是殺手，可看作他們是殺手的概率是相同的。?
問：根據最優的情況，保證警察自身安全并知道誰是殺手的概率最大是多少？
?
Sulotion
最優的詢問對象是，把強連通分量縮成一個點(問其中一個可推出所有，只要不第一次問就是罪犯可以一直安全)，問那些入度為0的(這里相當于再把連通的縮為一個點)。
這樣我們就得到了一些互不相干的點集，怎么計算概率呢？設點集大小為s1,s2,..
那么ans=(n-1)/n(第一次問不是罪犯)*[(s1-1/n-1)(集合在第一點集中)+((n-s1)/(n-1))*((n-s1-1)/(n-s1))*((s2-1)*(n-s1-1))(分別為，不在第一點集，第二次不問到罪犯，在第二點集的概率)+...]。
上面的式子分子分母可以連著消掉，然后得到ans=(n-tot)/n, tot為點集個數，也就是縮點后入度為0的點。
有一種特殊情況(連通題做一道一道特殊情況...)
如果有一個單獨地點(大小為1&&入度為0&&不影響其它點入度是否為0)，那么其他的都確定了，他自然也就可以肯定了，也不會對別的點有影響，不用算入tot。
?
Code
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int maxn=1e5+5,maxm=3e5+5; 5 6 int pre[maxn],low[maxn],scc[maxn],clock,cnt; 7 int head[maxn],f[maxm],e[maxm],nxt[maxm],k; 8 int adde(int u,int v){ 9 e[++k]=v,f[k]=u; 10 nxt[k]=head[u],head[u]=k; 11 } 12 int n,m,r[maxn],a[maxn],t; 13 int size[maxn],num[maxn]; 14 15 int dfs(int u){ 16 pre[u]=low[u]=++clock; 17 a[++t]=u; 18 for(int i=head[u];i;i=nxt[i]){ 19 int v=e[i]; 20 if(!pre[v]){ 21 dfs(v); 22 low[u]=min(low[u],low[v]); 23 } 24 else if(!scc[v]){ 25 low[u]=min(low[u],pre[v]); 26 } 27 } 28 if(low[u]==pre[u]){ 29 num[++cnt]=u; 30 while(t){ 31 scc[a[t]]=cnt; 32 size[cnt]++; 33 if(a[t--]==u) break; 34 } 35 } 36 } 37 38 int pd(int x){ 39 int u=num[x]; 40 for(int i=head[u];i;i=nxt[i]) 41 if(r[scc[e[i]]]==1) return 0; 42 return 1; 43 } 44 45 int main(){ 46 scanf("%d%d",&n,&m); 47 int u,v; 48 for(int i=1;i<=m;i++){ 49 scanf("%d%d",&u,&v); 50 adde(u,v); 51 } 52 53 for(int i=1;i<=n;i++) 54 if(!pre[i]) dfs(i); 55 56 for(int i=1;i<=k;i++) 57 if(scc[f[i]]!=scc[e[i]]) r[scc[e[i]]]++; 58 59 int ans=0; 60 for(int i=1;i<=cnt;i++) 61 if(!r[i]) ans++; 62 63 for(int i=1;i<=cnt;i++) 64 if(size[i]==1&&!r[i]&&pd(i)){ 65 ans--; 66 break; 67 } 68 69 printf("%.6lf",(double)(n-ans)/n); 70 return 0; 71 }
?
)
)
)
