本文主要是介绍【题解】洛谷P4819 [中山市选] 杀人游戏,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目传送门
题面描述:
一位冷血的杀手潜入 Na-wiat,并假装成平民。警察希望能在 N 个人里面,查出谁是杀手。警察能够对每一个人进行查证,假如查证的对象是平民,他会告诉警察,他认识的人, 谁是杀手, 谁是平民。
假如查证的对象是杀手, 杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手,可看作他们是杀手的概率是相同的。
问:根据最优的情况,保证警察自身安全并知道谁是杀手的概率最大是多少?
Input
第一行有两个整数 N,M。
接下来有 M 行,每行两个整数 x,y,表示 x 认识 y(y 不一定认识 x) 。
Output
仅包含一行一个实数,保留小数点后面 6 位,表示最大概率。
题意转化:有n个点,每个点都有一个身份。其中有 m m m个关系,每个关系给出 a a a和 b b b,表示 a a a认识 b b b( b b b不一定认识 a a a),求最少要询问多少个人,才能知道所有人的身份(把那个杀手找出来)。
分析:
- 我们要询问最少的人有什么用呢?
假设有 n n n个人,我们询问了 k k k个点知道了所有人的身份。但是,杀手有可能在这k个人之中,也就是说,我们在询问这 k k k个人的时候就被杀掉了。对于每个点,他是杀手的概率是 1 n \frac{1}{n} n1,我们询问了 k k k个人,概率就是 k n \frac{k}{n} nk。所以,我们被杀的概率是 k n \frac{k}{n} nk,能够存活的概率就是 1 − k n 1-\frac{k}{n} 1−nk。
题意理解了之后,我们再思考做法。
考虑样例:
我们只要访问 1 1 1号节点,就能知道全部的身份,1号节点是杀手的概率是 1 5 \frac{1}{5} 51,所以安全的概率就是 4 5 \frac{4}{5} 54。
那么样例太水,尝试来一个复杂一点的样例。
对于这个样例,我们只要访问1号节点知道2,3,4号点的身份和访问6号点知道5号点的身份就可以了。概率是 2 3 \frac{2}{3} 32。
- 现在我们已经大致理清楚了题意,但是题目上的图不免有些复杂了,我们能否尝试将图变得简单一点呢?
对于一个集合而言,如果访问了集合内的一个点就知道了集合内所有人的身份,那么这个集合中的点都是等价的,相当于一个点,那么我们只要把他们当成一个点即可。又联想到有向图,我们想到了什么?强连通分量!
没错,这道题就是一道强联通分量缩点的例题。
图就变得简洁多了,我们只要访问1号点和六号点即可。
第一个猜想:缩点后入度为0的点的个数就是所求的最小点数
恭喜你,那么整整21分!
来组反例:
那么对于这幅图,我们实际上只要访问一号点知道1,2,3,4号点的身份,通过排除法就可以得到5号点的身份。即我们只需要访问一个人就可以知道所有人的身份。
我们在猜想:对于缩点后的一个点,如果他的大小为1,入度为0,出去的所有的点的入度>1,那么这个点就可以不用访问,不过我们最多只能不访问这么一个节点(用排除法的性质就可以想)
我们在屡一下思路:
- 强联通分量缩点
- 找出入度为0的点数k
- 找出是否存在上述的特属于的点,记为布尔f
- 答案为 1 − k − f n 1-\frac{k-f}{n} 1−nk−f
那么具体代码如下:
#include<bits/stdc++.h>
using namespace std;
struct node{int x,y,Next;
}e[600010],e1[600010];
int linkk[600010];
int in[600010];
int linkk1[600010];
int dfn[600010];
int low[600010];
int stackk[600010];
int fam[600010];
int size[600010];
bool vis[600010];
int len=0,cnt=0,num=0,top=0,ans=0;
int n,m;
void insert(int x,int y){e[++len].Next=linkk[x];linkk[x]=len;e[len].y=y;e[len].x=x;
}
void insert2(int x,int y){e1[++len].Next=linkk1[x];linkk1[x]=len;e1[len].y=y;
}
void insert_new(){for (int i=1;i<=m;i++)if (fam[e[i].x]!=fam[e[i].y])insert2(fam[e[i].x],fam[e[i].y]),in[fam[e[i].y]]++;
}
void tarjan(int x){dfn[x]=low[x]=++cnt;stackk[++top]=x;vis[x]=1;for (int i=linkk[x];i;i=e[i].Next)if (!dfn[e[i].y])tarjan(e[i].y),low[x]=min(low[x],low[e[i].y]);else if (vis[e[i].y]) low[x]=min(low[x],dfn[e[i].y]);if (dfn[x]==low[x]){++num;int t;do{t=stackk[top--];vis[t]=0;size[num]++;fam[t]=num;}while (x!=t);}
}
int main(){scanf("%d %d",&n,&m);for (int i=1,x,y;i<=m;i++)scanf("%d %d",&x,&y),insert(x,y);for (int i=1;i<=n;i++)if (!dfn[i]) tarjan(i);len=0;insert_new();bool f=0;for (int i=1;i<=num;i++){bool ff=0;if (!f&&!in[i]&&size[i]==1){ff=1;for (int j=linkk1[i];j;j=e1[j].Next) if (in[e1[j].y]==1){ff=0;break;}}if (ff) f=1;if (!in[i]) ans++;}printf("%.6lf",1.0-double(double(ans-f)/double(n)));fclose(stdin);fclose(stdout);return 0;
}
这篇关于【题解】洛谷P4819 [中山市选] 杀人游戏的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!