BZOJ 2438：杀人游戏（tarjan+概率）

杀人游戏
Description
一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，查出谁是杀手。
警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。
现在警察掌握了每一个人认识谁。
每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。
问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？
Input
第一行有两个整数 N,M。
接下来有 M 行，每行两个整数 x,y，表示 x 认识 y（y 不一定认识 x,例如胡锦涛同志）。
Output
仅包含一行一个实数，保留小数点后面 6 位，表示最大概率。
Sample Input
5 4
1 2
1 3
1 4
1 5
Sample Output
0.800000
HINT
警察只需要查证 1。假如1是杀手，警察就会被杀。假如 1不是杀手，他会告诉警
察 2,3,4,5 谁是杀手。而 1 是杀手的概率是 0.2,所以能知道谁是杀手但没被杀的概
率是0.8。对于 100%的数据有 1≤N ≤ 10 0000,0≤M ≤ 30 0000

数据已加强！
Source

分析：

要想知道谁是凶手，必须要知道所有人的情况才行。

显然问的人越少警察越安全

如果一个人被询问，则他所连通的所有点都可知道，（理由很简单，一个人被问到，它认识的人中谁是好人也知道了，对于好人，我们可以放心大胆的问，这样联通的点信息全部知道了）

这样，本题转化为在一个有向图中，选出x个点使得从该这些点出发能遍历到所有点，要求x最小。

先tarjan缩点，然后统计入度为0的scc即可（一个scc与一个点等效，有凶手概率都是1/n）

这样就结束了吗，不是。这种看法存在漏洞，比如说三个人ABC，A认知B，在这种情况下，我只需要询问A（于是AB都知道了），然后推理出C即可。

所以我们要进行判断，如果存在一个点它入度出度为0，或入度为0，自己所连的点都有两个以上的入度（这样自己的后继可被其它点遍历而自己可被推理出来），则将x-1，注意只能进行一次。

输出（n-x)/n，保留6位小数即可。

注意：在一个scc有多边连同一点只算一次，每个scc只统计一次。

代码：

program play;

type

  point=^node;

   node=record

     x:longint; next:point;

   end;

var

  a:array[..]of point;

  f,low,dfn,q,w:array[..]of longint;

  g,instack:array[..]of boolean;

  n,i,m,s,t,num,x,y,ans:longint;

function min(x,y:longint):longint;

begin

  if x<y then min:=x else min:=y;

end;

procedure add(x,y:longint);

var p:point;

begin

  new(p); p^.x:=y; p^.next:=a[x]; a[x]:=p;

end;

procedure tarjan(x:longint);

var y:longint; p:point;

begin

  inc(s); low[x]:=s; dfn[x]:=s; inc(t); q[t]:=x;

  instack[x]:=true;

  new(p); p:=a[x];

  while p<>nil do

   begin

     y:=p^.x;

     if dfn[y]= then begin tarjan(y); low[x]:=min(low[x],low[y]); end

      else if instack[y]=true then low[x]:=min(low[x],dfn[y]);

     p:=p^.next;

   end;

  if dfn[x]=low[x] then

   begin

     inc(num);

     repeat

       y:=q[t]; dec(t); f[y]:=x;instack[y]:=false;

     until x=y;

   end;

end;

procedure scc;

var x,y:longint; p:point;

begin

  fillchar(g,sizeof(g),false);

  for x:= to n do

   begin

     new(p); p:=a[x];

     while p<>nil do

      begin

        y:=p^.x; g[f[y]]:=false; p:=p^.next;

      end;

     new(p); p:=a[x];

     while p<>nil do

      begin

        y:=p^.x;

        if (g[f[y]]=false)and(f[x]<>f[y]) then

         begin g[f[y]]:=true; inc(w[f[y]]); end;

        p:=p^.next;

      end;

   end;

end;

function cheak(x:longint):boolean;

var p:point; y:longint;

begin

  if w[x]<> then exit(false);

  new(p); p:=a[x];

  while p<>nil do

   begin

     y:=p^.x;

     if (f[x]=f[y])or(w[y]<=) then exit(false);

     p:=p^.next;

   end;

  exit(true);

end;

begin

  assign(input,'play.in');

reset(input);

assign(output,'play.out');

rewrite(output);

  readln(n,m);

  for i:= to m do

   begin

     readln(x,y); add(x,y);

   end;

  for i:= to n do begin dfn[i]:=; low[i]:=; w[i]:=; instack[i]:=false; end;

  s:=; t:=; num:=;

  for i:= to n do if dfn[i]= then tarjan(i);

  scc;

  for i:= to n do g[i]:=false;

  for i:= to n do

   if (w[f[i]]=)and(g[f[i]]=false) then begin inc(ans); g[f[i]]:=true; end;

  for i:= to n do if cheak(f[i])=true then begin dec(ans); break; end;

  writeln((n-ans)/n::);

  close(input); close(output);

end.

巴特西

BZOJ 2438：杀人游戏（tarjan+概率）

最新文章

热门文章