P4819 [中山市选] 杀人游戏 https://www.luogu.org/problem/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
来源: http://www.bubuko.com/infodetail-3268321.html