[P4819][中山市选]杀人游戏
🧷

[P4819][中山市选]杀人游戏

Created
Oct 15, 2020 01:00 PM
Tags
题解
洛谷
图论建模
Tarjan
Author
画外音:好久没写题解了,AC了这题就来写题解。但是这道题真的让我好失望,不是我所想象的Tarjan建模题……

题目链接:

题解:

这题不难。首先,假设我们已经查证了一个人并没有被杀,那么我们就可以知道他所有认识的人的信息。到这里,可以很自然地想到图论建模。每个人为一个节点,每个相识关系就是一条边。那么我们每过一个点就可以扩展到其相邻的所有点。而题目中要求让警察不被杀的可能性最大,因此就要使不确定查询(就是不确定查询对象是否是犯人的查询)的次数最小。那么我们可以求出图中的所有强连通分量,并缩点,然后找出所有入度为的点,这就是最少不确定查询次数,并可以顺利求出概率了。
很快写完了代码,过了样例,兴冲冲地交上去,觉得可以,结果:分???
我看了一下洛谷上的错误报告,发现我有输出为的情况,经分析,发现:
如果只有两个人,他们互相都不认识,查过一个人,发现他不是犯人,那么作为一个有脑子的警察,他可能再去查另外一个人去送死吗?
那么,也就是说,如果我们能找出这样一个“与世隔绝”的点(缩完点后的点),且其本身大小为,那么,我们就可以不去查那个点。
问题来了,怎么定义”与世隔绝“呢?一个点是与世隔绝的充分必要条件就是:
  1. 该点的大小
  1. 该点的入度
  1. 通过这个点所能到达的点的入度都不为
大家可以自己思考一下其正确性,画个图看看就行了。
下面附上可爱的代码:
//File: P4819.cpp
//Author: yanyanlongxia
//Date: 2020/8/9
//[中山市选]杀人游戏
#include <bits/stdc++.h>

using namespace std;
int n,m,dfn[300005],low[300005],head[300005],nxt[300005],ver[300005],bel[300005],sz[300005],sccn,tot,dft,din[300005];
stack<int>st;
bool in[300005];
double per;
int nver[300005],nnxt[300005],nhead[300005],ntot;//缩点后的新图
void add(int x,int y)
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void new_add(int x,int y)
{
    nver[++ntot]=y;
    nnxt[ntot]=nhead[x];
    nhead[x]=ntot;
}
void tarjan(int x)
{
    dfn[x]=low[x]=++dft;
    st.push(x);
    in[x]=true;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else
        {
            if(in[y])
                low[x]=min(low[x],dfn[y]);
        }
    }
    if(low[x]==dfn[x])
    {
        int y;
        sccn++;
        do {
            y=st.top();
            st.pop();in[y]=false;
            bel[y]=sccn;
            sz[sccn]++;//强连通分量的大小
        }while (x!=y);
    }
}
int main() {
    int x, y;
    scanf("%d%d", &n, &m);
    per = (double) 1 / n;//注意这里的1前面要加double
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= n; i++)
        for (int j = head[i]; j; j = nxt[j]) {
            if (bel[i] != bel[ver[j]]) {
                new_add(bel[i], bel[ver[j]]);//建立缩点图
                din[bel[ver[j]]]++;//统计入度
            }
        }
    int cnt = 0;
    bool p = 0;
    for (int i = 1; i <= sccn; ++i) {
        if (din[i] == 0) {
            cnt++;//统计入度为0的点
            if(sz[i]==1)//大小为1
            {
                int ct1=0;
                for(int j=nhead[i];j;j=nnxt[j])
                {
                    int k=nver[j];
                    if(din[k]==1)//入度是否为1
                        ct1++;
                }
                if (ct1==0)
                    p=1;
            }
        }
    }
    if (p)
        cnt--;
    double ans = (double)cnt * per;
    ans = (double)1 - ans;
    printf("%.6lf", ans);
    return 0;
}
:我什么时候·开启了狂刷水题模式……

Loading Comments...