做网站建设公司crm在线的提升服务,网站建设销售开场白,湖南常德邮编,如何查看一个网站的访问量正题
题目链接:https://www.luogu.com.cn/problem/P4819 题目大意 nnn个人#xff0c;一个杀手#xff0c;搜查一个平民可以知道他认识的人的身份#xff0c;搜查杀手就会死#xff0c;求最优情况下警察的最低死亡概率。 解题思路
先用tarjantarjantarjan搜出强连通…正题
题目链接:https://www.luogu.com.cn/problem/P4819 题目大意
nnn个人一个杀手搜查一个平民可以知道他认识的人的身份搜查杀手就会死求最优情况下警察的最低死亡概率。 解题思路
先用tarjantarjantarjan搜出强连通然后搜查其中一个就是可以知道强连通中的所有人。
所有缩点后求出入度为0的点的度数即可。
但是有一种情况就是知道其他人的身份都是平民那么剩下一个一定是杀手所以我们如果有一个点入度唯一缩点前任然是一个点且连接的点入度都为不为1的话那么搜查的人就可以少一个。
时间复杂度O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includestack
using namespace std;
const int N1e510;
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];
stackint S;
void addl(int x,int y){a[tot].toy;a[tot].fromx;a[tot].nextls[x];ls[x]tot;
}
void tarjan(int x){dfn[x]low[x]tot;S.push(x);ins[x]1;for(int ils[x];i;ia[i].next){int ya[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 yS.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 i1;in;i)siz[i]1,fa[i]i;for(int i1;im;i){int x,y;scanf(%d%d,x,y);addl(x,y);}for(int i1;in;i)if(!dfn[i])tarjan(i);tot0;memset(ls,0,sizeof(ls));for(int i1;im;i){int xa[i].from,ya[i].to;if(fa[x]!fa[y]){in[fa[y]];addl(fa[x],fa[y]);}}for(int i1;in;i){if(fa[i]!i)continue;if(!flag!in[i]siz[i]1){bool z1;for(int jls[i];j;ja[j].next)if(in[a[j].to]1){z0;break;}if(z)flag1;}if(!in[i])ans;}if(flag)ans--;printf(%.6lf,1.0-1.0*ans/n);
}
