题目描述
有向图中有若干白点和一个黑点,每个点为黑点概率相等。每次可以任选一个点发起询问,询问结果为该点能直接到达的所有点颜色。
求最优情况下不对黑点发起询问且得知黑点标号的概率。
解法
首先考虑连通性。容易发现的一条性质:如果对某个强连通分量中的任意一点发起询问,只要该点不是黑点,我们就能在没有任何风险的情况下得知该强连通分量中所有点的颜色。
因此可以确定解决本题的第一个步骤:缩点,将所有强连通分量看作一个点。此时图转化为一张 $DAG$。
继续思考。在得到的 $DAG$ 中,如果某个点有入边,那么与其先询问该点,不如先对向该点有出边连接的点发起询问。原因很简单:如先对该点发起询问,那么我们无法得知向该点有出边连接的点的颜色,之后一定需要向上发起另一次询问,这样会有更大的风险。同时,如果当前点是黑点,先询问该点会直接失败,而如果先询问向该点有出边连接的点,我们就会在询问黑点前就得知黑点的标号。综上所述,询问向该点有出边连接的点显然更划算。
因此可以得出一个结论:在新图中,我们只需要对入度为 $0$ 的点发起可能遇到黑点的询问。如果在这些询问中没有遇到黑点,之后的询问就绝对安全了。
我们可以依据这个结论对答案进行猜测:设缩点后新图中入度为 $0$ 的点数量为 $c$,则答案应为 $1-\frac{c}{n}$。
这个答案已经很接近正解了,但并不完全正确,仍然有特殊情况存在。
考虑原图中一个单独的点 $p$。若 $p$ 的入度为 $0$,且 $p$ 可直接到达的所有点入度均$\geq2$(或者 $p$ 没有出边),此时如果我们把 $p$ 置于询问队列的最后,那么在对 $p$ 发起询问之前,与 $p$ 相连的所有点的颜色都已经确定了。如果黑点在这些点当中,我们自然没有必要再对 $p$ 进行询问了。如果最后我们仍没有确定黑点标号,那么 $p$ 是黑点,同样无需对 $p$ 发起询问。
因此,如果图中存在至少一个入度为 $0$ 且 $size=1$ 的强连通分量,答案就会变为 $1-\frac{c-1}{n}$,注意答案只能变化一次。
解题思路到这里就整理完毕了,但代码实现上还有一点小问题:在原图中,一个点可能有多条连接某一其他强连通分量的出边。这样一来缩点过后会出现重边,有可能会导致统计答案的过程中误判一些点的入度而出现错误。本题中已有的另一篇题解就没能解决这个问题。
解决这个问题略显困难。我原本的思路是开 $map$ 保存连接状况,这样的做法可以通过,但速度相当慢。有关这个问题的解法,蓝书的光盘中给了一种优秀的思路:缩点时枚举每个点的出边,连边的同时给每个强连通分量打标记,枚举完当前点的所有出边后把标记去掉。
至此,本题得到完美的解决。
C++代码
#include<cstdio>
#include<map>
int dfn[300086],low[300086],h[300086],hh[300086],inv[300086],col[300086],st[300086],sze[300086];
int n,m,tot,cnt,top,u,v,C,dfncnt;
bool vis[300086],vv[300086];
struct asdf{
int v,nxt;
}e[600086],ee[600086];
struct asd{
int u,v;
}E[300086];
int read(){
char ch=getchar();int nn=0,ssss=1;
while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
return nn*ssss;
}
bool add(int u,int v){
e[++tot].v=v;
e[tot].nxt=h[u];
h[u]=tot;
return true;
}
bool addedge(int u,int v){
ee[++tot].v=v;
ee[tot].nxt=hh[u];
hh[u]=tot;
inv[v]++;
return true;
}
bool tarjan(int np){
dfn[np]=low[np]=++dfncnt;
st[++top]=np;vis[np]=true;
for(int i=h[np];i;i=e[i].nxt){
if(!dfn[e[i].v]){
tarjan(e[i].v);
if(low[e[i].v]<low[np])low[np]=low[e[i].v];
}
else
if(vis[e[i].v]&&dfn[e[i].v]<low[np])low[np]=dfn[e[i].v];
}
if(low[np]==dfn[np]){
C++;
while(st[top+1]!=np){
vis[st[top]]=false;
col[st[top]]=C;
sze[C]++;
top--;
}
}
return true;
}
int main(){
n=read();m=read();
for(int i=1;i<=m;i++){
scanf("%d%d",&E[i].u,&E[i].v);
add(E[i].u,E[i].v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
tot=1;
for(int i=1;i<=n;i++){
for(int j=h[i];j;j=e[j].nxt){
if(col[i]==col[e[j].v]||vv[col[e[j].v]])continue;
addedge(col[i],col[e[j].v]);
vv[col[e[j].v]]=true;
}
for(int j=h[i];j;j=e[j].nxt)vv[col[e[j].v]]=false;
}
bool flag=true;
for(int i=1;i<=C;i++){
if(!inv[i])cnt++;//统计无入边的点
if(inv[i]||sze[i]>1)continue;
if(flag){
bool pp=true;
for(int j=hh[i];j;j=ee[j].nxt)
if(inv[ee[j].v]<=1){
pp=false;
break;
}
if(pp)cnt--,flag=false;//如果某个强连通分量size为1且指向的点入度均>1,则该点可以不访问
}
}
printf("%.6lf",(double)(n-cnt)/n);
}
最优情况下是什么意思啊,我有点没读懂题目hhh
%
请问这个去重为什么是对的啊。
比如这个,这么连的话两个强联通分量还是会有重边?
是的,但是这样的重边不会影响答案统计
谢谢!
義已失吾亦死
码了好多字,有没讲明白的欢迎提出