中山市选杀人游戏

wjh15101051's space

卧薪尝胆，厚积薄发。

中山市选杀人游戏

Date: Thu Sep 13 09:48:03 CST 2018

In Category: NoCategory

Description：

$n$ 个人之中有一个人是杀手，警察可以选择调查一些人，如果是杀手会把警察干掉，否则会告诉你谁是杀手，问根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少。

$1\le n \le 100000$

Solution：

首先答案一定是 $1-$ 调查的人的个数 $\times \frac 1 n$ 。

只要调查入度为零的强连通分量中的一个人就够了，最终答案就是 $1-$ 入度为零的强连通分量个数 $\times\frac 1 n$ 。

然而如果存在一个强连通分量只是一个点，他要么没有出边，要么所有出边的强连通分量入度都不为 $1$ ，也就是说不用调查他也可以判断其他人的情况，那么就可以通过排除法少调查一个人。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<vector>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

#define MAXM 300010

struct edge

{

	int to,nxt;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int dfn[MAXN],low[MAXN],tot = 0;

int siz[MAXN],ins[MAXN],scc = 0;

bool v[MAXN];

stack<int> s;

void tarjan(int k)

{

	dfn[k] = low[k] = ++tot;

	v[k] = true;s.push(k);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(dfn[e[i].to] == 0)

		{

			tarjan(e[i].to);

			low[k] = min(low[k],low[e[i].to]);

		}

		else if(v[e[i].to])

		{

			low[k] = min(low[k],dfn[e[i].to]);

		}

	}

	if(low[k] >= dfn[k])

	{

		int t;

		++scc;

		do

		{

			t = s.top();s.pop();

			ins[t] = scc;siz[scc] += 1;

			v[t] = false;

		}while(t != k);

	}

	return;

}

vector<int> g[MAXN];

int ind[MAXN];

bool single(int k)

{

	for(int i = 0;i < g[k].size();++i)

	{

		if(ind[g[k][i]] == 1)return false;

	}

	return true;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

	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] == 0)tarjan(i);

	}

	for(int k = 1;k <= n;++k)

		for(int i = lin[k];i != 0;i = e[i].nxt)

			if(ins[k] != ins[e[i].to])

			{

				g[ins[k]].push_back(ins[e[i].to]);

				++ind[ins[e[i].to]];

			}

	int ans = 0;

	bool have_one = false;

	for(int i = 1;i <= scc;++i)

	{

		if(!have_one && ind[i] == 0 && siz[i] == 1 && single(i))have_one = true;

		if(ind[i] == 0)++ans;

	}

	if(have_one)--ans;

	printf("%.6lf\n",1.0 - (double)ans / (double)n);

	return 0;

}

In tag: 图论-tarjan

wjh15101051