正題

題目鏈接:https://www.luogu.com.cn/problem/P4819

---

題目大意

$n$個人，一個殺手，搜查一個平民可以知道他認識的人的身份，搜查殺手就會死，求最優情況下警察的最低死亡概率。

---

解題思路

先用$tarjan$搜出強連通，然后搜查其中一個就是可以知道強連通中的所有人。

所有縮點后求出入度為0的點的度數即可。

但是有一種情況就是知道其他人的身份都是平民，那么剩下一個一定是殺手，所以我們如果有一個點入度唯一，縮點前任然是一個點，且連接的點入度都為不為1的話那么搜查的人就可以少一個。

時間復雜度$O(n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> using namespace std; const int N=1e5+10; struct node{int to,from,next; }a[N*3]; int n,m,tot,ans,ls[N],in[N]; int siz[N],fa[N],dfn[N],low[N]; bool flag,ins[N]; stack<int> S; void addl(int x,int y){a[++tot].to=y;a[tot].from=x;a[tot].next=ls[x];ls[x]=tot; } void tarjan(int x){dfn[x]=low[x]=++tot;S.push(x);ins[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(!dfn[y]){tarjan(y);low[x]=min(low[x],low[y]);}else if(ins[y])low[x]=min(low[x],dfn[y]);}if(low[x]==dfn[x]){while(S.top()!=x){int y=S.top();fa[y]=x;siz[x]++;S.pop();ins[y]=0;}ins[x]=0;S.pop();}return; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)siz[i]=1,fa[i]=i;for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);tot=0;memset(ls,0,sizeof(ls));for(int i=1;i<=m;i++){int x=a[i].from,y=a[i].to;if(fa[x]!=fa[y]){in[fa[y]]++;addl(fa[x],fa[y]);}}for(int i=1;i<=n;i++){if(fa[i]!=i)continue;if(!flag&&!in[i]&&siz[i]==1){bool z=1;for(int j=ls[i];j;j=a[j].next)if(in[a[j].to]==1){z=0;break;}if(z)flag=1;}if(!in[i])ans++;}if(flag)ans--;printf("%.6lf",1.0-1.0*ans/n); }

總結

以上是生活随笔為你收集整理的P4819-[中山市选]杀人游戏【tarjan】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。