P4819 [中山市选]杀人游戏
分析:
这种题先从简单情况分析:如果是一条链:1->2->3->4
直接查入度为0的即可:因为知道1,就知道2,如果2是杀手,结束。
否则去查证2(因为已知2不是杀手 所以这一步是不需要花费被杀的风险的!!)
以此类推。
最后的答案就是1-(1/n)*ans
一条链只需要查一个入度为0的点,那么如果有一个孤立的环呢?
显然需要查环中任意一个点即可。所以可以用tarjan缩点后,求入度为0的点即可。
但是这道题还有很多其他的坑:
eg:100 0
如果前99个人都查完了,第100个人就可以不用查了
考虑什么时候可以不用查:当一个点入度为0,并且它连的所有点入度都不为1(也就是说其他点可以通过另一个入度为0的点查到)
并且它的siz==1(是一个孤立的点,否则环中必须查一个点)
特判一下即可。
#include<bits/stdc++.h> using namespace std; #define ri register int #define N 100005 int n,m,dfn[N],low[N],stk[N],flag[N],bel[N],ru[N],Ti=0,tot=0,top=0,siz[N]; vector<int> e[N]; vector<int> h[N]; void tarjan(int u) { dfn[u]=low[u]=++Ti; stk[++top]=u; flag[u]=1; for(ri i=0;i<e[u].size();++i){ int v=e[u][i]; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); } else if(flag[v]) low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]){ tot++; do{ int tmp=stk[top]; flag[tmp]=0; bel[tmp]=tot; siz[tot]++; }while(stk[top--]!=u); } } int main() { scanf("%d%d",&n,&m); int a,b; for(ri i=1;i<=m;++i) scanf("%d%d",&a,&b),e[a].push_back(b); for(ri i=1;i<=n;++i) if(!dfn[i]) tarjan(i); for(ri i=1;i<=n;++i){ for(ri j=0;j<e[i].size();++j){ int v=e[i][j]; if(bel[i]==bel[v]) continue; h[bel[i]].push_back(bel[v]); ru[bel[v]]++; } } int fl=0,ans=0; for(ri i=1;i<=tot;++i) if(!ru[i]){ ans++; if(fl || siz[i]>1) continue; fl=1; for(ri j=0;j<h[i].size();++j) if(ru[h[i][j]]<2) { fl=0; break;} } //printf("%d\n",ans-fl); printf("%.6lf\n",(1-(1.0/n)*(double)(ans-fl))); return 0; } /* 6 5 1 2 1 3 4 2 5 2 6 2 4 3 1 2 2 3 3 4 */View Code