P4819 题解

题意简述

\(n\) 个居民中有一名杀手，有些居民知道其他一些人的身份是杀手还是平民，该类条件共 \(m\) 条。现在警方要询问一些居民来获得其他人的信息，要求在能够从已知条件推断出杀手是谁的前提下询问尽可能少的人。然而每个居民是杀手的概率都是 \(\frac{1}{n}\)，因此警方询问的居民中可能就有杀手，从而被杀。求询问最少人的情况下警察生还的几率。

题目分析

很明显，题目的条件可以构成一个 \(n\) 个顶点、\(m\) 条边的有向图 \(G=(V,E)\)。因此问题转换为：在该有向图中找到最少的点，使得从这些点出发可以到达所有 \(n\) 个点或者其中的 \(n-1\) 个点。而之所以到达其中的 \(n-1\) 个点就满足题意，是因为当“知道” \(n-1\) 个点的“身份”时，杀手只可能是剩下的一个点或者在这 \(n-1\) 个点其中。因此设答案取的点的点集为 \(V'\subseteq V\)，假设 \(G\) 是一个 DAG，则满足：令 \(A=\{j\in V |\exists i \in V',(i,j) \in E\}, |A|=n-1\) 或 \(n\)

显然，为了满足最优性，点集 \(V'\) 中的所有点的入度为 0（请自行思考原因）。不过，因为 \(G\) 不一定是一个 DAG，所以我们可以对其进行 tarjan 强连通分量缩点，这里将其作为基础知识不再赘述，如果不了解其过程及原理请查阅相关资料：【洛谷日报第 27 期】初探tarjan算法（求强连通分量）。

我们再来讨论一下 \(V'\) 的求法。如果存在 1 个点满足入度为 0 并且该点连向的所有点的入度都大于 1（也就是从其他入度为 0 的点出发可以到达），那么就说明可以不将这个“无用”的点放入 \(V'\) 。注意，该类点如果有多个则只能去除一个，其他的点仍需要放入 \(V'\) 。综上，原题的答案就是 \(\frac{|V'|}{n}\)，时间复杂度为 \(O(n+m)\)。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100010,MAXM=300010;
int m,n,a,b,ans;
int nt[MAXM],hd[MAXN],v[MAXM],tot;
int nt2[MAXM],hd2[MAXN],v2[MAXM],tot2,ru[MAXN];
int dfn[MAXN],low[MAXN],C[MAXN],cnt,num,stk[MAXN],top,sz[MAXN];
bool ins[MAXN];
void add(int x,int y)
{
  v[++tot]=y;
  nt[tot]=hd[x];
  hd[x]=tot;
}
void add2(int x,int y)
{
  v2[++tot2]=y;
  nt2[tot2]=hd2[x];
  hd2[x]=tot2;
  ru[y]++;
}//建新图 
inline void tarjan(int x)//tarjan 求强连通分量 
{
  dfn[x]=low[x]=++cnt;
  stk[++top]=x;
  ins[x]=1;
  for(int i=hd[x]; i; i=nt[i])
  {
    int y=v[i];
    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])
  {
    int y;
    num++;
    do
    {
      y=stk[top--];
      ins[y]=0;
      C[y]=num;
      sz[num]++;
    }
    while(x!=y);
  }
}
bool pd(int x)//判断该点是否满足入度为 0 并且连向的所有点的入度都大于1 
{
  if(!ru[x]&&sz[x]==1)
    for(int i=hd2[x]; i; i=nt2[i])
    {
      int y=v2[i];
      if(ru[y]==1)
        return 0;
    }
  return !ru[x]&&sz[x]==1;
} 
int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1; i<=m; i++)
  {
    scanf("%d%d",&a,&b);
    add(a,b);
  }
  for(int i=1; i<=n; i++)
    if(!dfn[i])
      tarjan(i);
  memset(ins,0,sizeof ins);
  for(int x=1; x<=n; x++)//缩点 
  {
    for(int i=hd[x]; i; i=nt[i])
    {
      int y=v[i];
      if(C[x]!=C[y]&&!ins[C[y]])
      {
        ins[C[y]]=1;
        add2(C[x],C[y]);
      }
    }
    for(int i=hd[x]; i; i=nt[i])
    {
      int y=v[i];
      ins[C[y]]=0;
    }//注意该题缩点不能有重边 
  }
  for(int i=1; i<=num; i++)
    if(!ru[i])
      ans++;//初始答案点集就是缩点后入度为 0 的点。 
  for(int i=1; i<=num; i++)
    if(pd(i))
    {
      ans--;
      break;
    }//去掉“无用点”。 
  printf("%.6lf",(double)(n-ans)/n);
  return 0;
}