杀人游戏

杀人游戏

具有一定思维含量的tarjan。自然难点在tarjan之后的操作。

思路

看到认识关系想到建图,还是有向图考虑是否会与tarjan有关,发现在同一个scc中选择任何一个点,只要它是平民,就可以毫无风险的了解其他人的情况。(稍微解释一下:if选择的人是杀手警察就被干掉了,if选择的人是平民,那么你直接了解的人就全知道了,如果有杀手就结束了,如果没有就在SCC中继续循环直到走完scc或有杀手。肯定不会问到杀手,很安全)。根据这个性质一个scc就等价于一个点,进行缩点后形成DAG。

继续考虑,该从哪里进行查证。还是延用scc中使用的思考思路,同理,我们从任意一个DAG开始查证的话,只要不是杀手就可以无风险的走完这条路径(间接到达的所有点),那么我们只要每次查证的路径够长或者说查证次数够少,风险自然就低了。

我们就有了一个初步的想法,查证所有没有入度的点即可。最大概率就是\(1-\frac{tot}{n}\)。此题基本得到解决,但是还有一些细节需要考虑。比较难想到,但是我们可以想一下进行推理时,我们真的需要查证了所有人吗?比如已经得知n-1人都是平民,那么最后一人铁定是杀手根本不需要去查证。考虑什么时候会出现这种情况?容易想到是孤立点时可以少查证一次,能不能再通过这种特殊情况联想到其他特殊情况呢?例如这种情况:杀人游戏

red点就不需要查证啦,虽然入度为0,但下面的点可以完全替代它,而且也可以在最后推理出它。总结一下特判情况:孤立点,入度为0点且所有它直接到的点的入度均大于等于2(即别的点可以替代它)。此时答案为\(1-\frac{tot-1}{n}\)。

代码

需要注意一下重边的处理,因为可能一个点向同一个其他scc连多个边导致入度出现错误,判断出现问题。
我判重边是简单类哈希一下,用set维护。

int n,m,tot,flg;
int h[N],e[M],ne[M],din[N],idx;
int dfn[N],low[N],timestamp;
int id[N],sz[N],scc_cnt,stk[N],top;
bool in_stk[N];
vector<int> vec[N];
set<ull> s;

inline void add(int a,int b){...}
inline void tarjan(int u)
{...}

inline bool check(int a,int b)
{
	ull tmp = (ull)Hash * a + b;
	if(!s.count(tmp)){
		s.insert(tmp);
		return true;
	}
	return false;
}

signed main()
{
	n = read();m = read();
	for(int i = 0;i <= n;i++) h[i] = -1;
	for(int i = 1;i <= m;i++){
		int a,b;
		a = read();b = read();
		add(a,b);
	}
	for(int i = 1;i <= n;i++)
	   if(!dfn[i]) tarjan(i);
	for(int u = 1;u <= n;u++)
	   for(int i = h[u];~i;i = ne[i]){
	   	int j = e[i];
	   	int a = id[u],b = id[j];
	   	if(a != b && check(a,b)) din[b]++,vec[a].push_back(b);
	   }
	for(int i = 1;i <= scc_cnt;i++){
		if(!din[i]) tot++;
		if(!din[i] && sz[i] == 1 && !vec[i].size()) flg += 2;
		else if(!din[i] && sz[i] == 1){
			bool ck = false;
			for(int o = 0;o < vec[i].size();o++)
			   if(din[o] == 1){
			   	ck = true;
			   	break;
			   } 
			if(!ck) flg++;
		}
	}
	if(flg >= 2) tot--;
	printf("%.6lf\n",1 - 1.0 * tot / n);
}

如有错误,请指正。

上一篇:CF1559D Mocha and Diana 题解


下一篇:区间修改主席树