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

· · 题解

题目链接：[中山市选]杀人游戏

​ 本题的初始问题可以理解为：选择若干个点从而使得以选择点为起点，保证得知随机分布的特殊点位置的前提下，使得不选择特殊点的概率最大。

​ 对于任意的选择方案，假设选择 c 个点，那么在n点中选择到该特殊点的概率即为 \dfrac{c}{n} ，因此成功获取身份，即不选择特殊点的概率为 1-\dfrac{c}{n} 因此，问题转化为了最小化选择的点数 c

在原图上直接进行求解相对较为困难，此时便可考虑缩点。

​ 先讨论缩点的正确性，在任意一个强联通分量中，假设一个点已知身份，那么等同于强联通分量中其余点均知道身份，同时在强联通分量中任意选择一个点，是特殊点的概率也是等同的，因此强联通分量在目前转化的问题当中，可以理解成一个点。

​ 问题进一步转化为在 DAG 上取任意的点数量使得所有点被确定，在此有一个注意点：使得所有点被确定并不等同与通过连通关系覆盖所有的点，假设在未缩点原图当中有且只有一个点未被覆盖，那么此点的身份是可确定的。

​ 拓展到缩点后的 DAG 上，问题再次转化为最小化 DAG 选择的点，使得至多只有一个 \text{size}=1 的点不被确定。

​ 对于单独的限制情况比较难讨论，因此先讨论对于覆盖所有点的情况下，对于所有入度为 0 的点是必定要选择的，而入度不为 0 的点必然可以通过入度为 0 的点传导，因此答案为入度为 0 的点的个数。

​ 而加上限制后若要少取点，则也是尽量要少取入度为 0 的点，对于任意的入度为 0 且 \text{size}=1 的点，需要满足不选此点对于别的点的选取没有影响，即此点所连出的边至少还可以通过另一条边传导过来，即对于该点，任意的 in_{to}\ge2，该图便可以满足少选一个点的条件。

​ 关于本题的细节处理，在缩点后的连边，对于重边的连接可能会影响入度的计算，因此代码采用了 map 存已经出现过的边。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int dfn[N],low[N],s[N],in[N],out[N],siz[N],color[N],n,m,r,cnt,col;
bool flag[N];vector<int> g[N],e[N];map<pair<int,int>,bool> mp;

void tarjan(int p)//缩点模板，同时维护了缩点后代表的强联通分量点数目 
{
    dfn[p]=low[p]=++cnt;
    flag[p]=true;s[++r]=p;
    for(int i=0;i<g[p].size();i++)
    {
        int to=g[p][i];
        if(!dfn[to])
        {
            tarjan(to);
            low[p]=min(low[p],low[to]);
        }
        else
            if(flag[to])
                low[p]=min(low[p],dfn[to]);
    }
    if(dfn[p]==low[p])
    {
        col++;
        while(r&&s[r+1]!=p)
        {
            color[s[r]]=col;siz[col]++;
            flag[s[r--]]=false;
        }
    }
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1,u,v;i<=m;i++)
    {
        scanf("%d %d",&u,&v);
        g[u].push_back(v);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++)//连边+去重边 
        for(int j=0;j<g[i].size();j++)
            if(color[i]!=color[g[i][j]])
                if(mp.find(make_pair(color[i],color[g[i][j]]))==mp.end())
                {
                    in[color[g[i][j]]]++;
                    e[color[i]].push_back(color[g[i][j]]);
                    mp[make_pair(color[i],color[g[i][j]])]=true;
                }
    bool flag=false;int sum=0;
    for(int i=1;i<=col;i++)
    {
        if(!in[i])//统计入度为0的初始选择点 
            sum++;
        if(!in[i]&&siz[i]==1)//统计是否可以少选一个点
        {
            bool tmp=true;
            for(int j=0;j<e[i].size();j++)
                tmp&=(in[e[i][j]]>=2);
            flag|=tmp;
        }
    }
    if(flag)
        printf("%.6lf",1.0*(n-sum+1)/n);
    else
        printf("%.6lf",1.0*(n-sum)/n);
}