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

题目就是让我们在DAG中找到一些点，覆盖所有点。

因为是DAG，可以想到tarjan缩一下点。假设我们需要找x个点，那么答案就是(n-x)/n。

我们怎么选点呢？

敏锐的我们很快就能想到，直接选出所有入度为0的点。

但是，当我们发现一个入度为0的点，但是其中元素为1，而它的出边所到的点的入度都>1，则x--。

因为它们可以被别的点更新。

code：

#include <bits/stdc++.h>

using namespace std;

const int N=100010;

const int M=300010;

int n,m;

int s[M][2],o[N];

int low[N],dfn[N],sccno[N],scc,dfscnt,w[N];

int sta[N],top;

struct Edge {

    int next,to;

}e[M];

int last[N],len,in[N],ans;

char buffer[M],*S,*T;

inline char Get_Char()

{

    if(S==T)

    {

        T=(S=buffer)+fread(buffer,1,M,stdin);

        if(S==T) return EOF;

    }

    return *S++;

}

int Get_Int()

{

    char c;

    int re=0;

    for(c=Get_Char();c<'0'||c>'9';c=Get_Char());

    while(c>='0'&&c<='9')

           re=(re<<1)+(re<<3)+(c^48),c=Get_Char();

    return re;

}

void add(int x,int y)

{

    s[++o[0]][0]=y,s[o[0]][1]=o[x],o[x]=o[0];

}

void tarjan(int x)

{

    sta[++top]=x;

    low[x]=dfn[x]=++dfscnt;

    for (int i=o[x];i;i=s[i][1]) {

        int y=s[i][0];

        if (!dfn[y])

            tarjan(y),low[x]=min(low[x],low[y]);

        else if (!sccno[y])

            low[x]=min(low[x],dfn[y]);

    }

    if (dfn[x]==low[x]) {

        ++scc;

        while (1) {

            int y=sta[top--];

            sccno[y]=scc;

            ++w[scc];

            if (x==y) break;

        }

    }

}

void add2(int x,int y)

{

    e[++len].to=y,e[len].next=last[x],last[x]=len;

}

int main()

{

    int x,y;

    n=Get_Int(),m=Get_Int();

    if (!m) {printf("%.6lf",1.0/n);return 0;}

    if (n==1) {puts("1.000000");return 0;}

    for (int i=1;i<=m;++i)

        x=Get_Int(),y=Get_Int(),add(x,y);

    for (int i=1;i<=n;++i)

        if (!dfn[i]) tarjan(i);

    for (x=1;x<=n;++x)

        for (int i=o[x];i;i=s[i][1]) {

            y=s[i][0];

            if (sccno[x]!=sccno[y]) {

                add2(sccno[x],sccno[y]);

                ++in[sccno[y]];

            }

        }

    bool flag=0;

    for (x=1;x<=scc;++x) {

        if (w[x]==1&&in[x]==0) {

            bool k=0;

            for (int i=last[x];i;i=e[i].next) {

                y=e[i].to;

                if (in[y]>1) k=1;

                else {k=0;break;}

            }

            if (k) flag=1;

        }

        if (flag) {--ans;break;}

    }

    for (int i=1;i<=scc;++i)

        if (!in[i]) ++ans;

    double tmp=(n-ans)*1.0/n;

    printf("%.6lf",tmp);

    return 0;

}

巴特西

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

最新文章

热门文章