首页 > 代码库 > BZOJ 2438 杀人游戏（强连通分量）

BZOJ 2438 杀人游戏（强连通分量）

2024-07-09 00:02:37   231人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2438

题意：一位冷血的杀手潜入某村庄，并假装成 平民。警察希望能在 N 个人里面，查出谁是杀手。 警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人， 谁是杀手， 谁是平民。 假如查证的对象是杀手， 杀手将会把警察干掉。 现在警察掌握了每一个人认识谁。 每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。 问：根据最优的情况，保证警察自身 安全并知道谁是杀手的概率最大是多少？

思路：首先，求一次强连通分量SCC。那么 在一个SCC里知道了一个其他就都知道了。然后重新建图就得到一个有向无环图DAG。在这个DAG里，我们只要去询问那些入度为0的点即可。但是，有一种 特殊情况，就是我们假设知道了n-1个人是或不是杀手，那么另外那一个人即便他的入度为0也是不需要询问的。这样的人存不存在我们只需要判断它的孩子的入 度即可。若它的所有孩子的入度均大于1，也就是它的所有孩子都可由其他点遍历到，那么这个点就是不用询问的。而且这样的点即使有多个也只能算一次。

 

vector<int> g[N];int dfn[N],low[N],id,num,color[N],size[N],visit[N];stack<int> St;void DFS(int u){    dfn[u]=low[u]=++id; St.push(u);    int i,v;    FOR0(i,SZ(g[u]))    {        v=g[u][i];        if(!dfn[v]) DFS(v),upMin(low[u],low[v]);        else if(!visit[v]) upMin(low[u],dfn[v]);    }    if(dfn[u]==low[u])    {        num++;        do        {            v=St.top(); St.pop();            visit[v]=1;            color[v]=num;            size[num]++;        }while(u!=v);    }}int n,m;set<i64> S;vector<int> G[N];int ind[N];int main(){    RD(n,m);    int i,j,x,y;    FOR1(i,m) RD(x,y),g[x].pb(y);    FOR1(i,n) if(!visit[i]) DFS(i);    i64 temp;    FOR1(i,n) FOR0(j,SZ(g[i]))    {        x=g[i][j];        if(color[x]==color[i]) continue;        temp=(i64)color[i]*(n+1)+color[x];        if(S.find(temp)!=S.end()) continue;        S.insert(temp);        G[color[i]].pb(color[x]);        ind[color[x]]++;    }    double ans=1,det=1.0/n;    int flag=1;    FOR1(i,num) if(!ind[i])    {        if(size[i]==1)        {            FOR0(j,SZ(G[i])) if(ind[G[i][j]]==1) break;            if(flag&&j>=SZ(G[i])) flag=0;            else ans-=det;        }        else ans-=det;    }    PR(ans);}

 

 

 


联系
我们