[BZOJ 2438] [中山市选2011]杀人游戏 Tarjan缩点

这个题很容易想到正解就是缩点找入度为零的点，那么我们考虑一种特殊情况就是，一个入度为零的点我们不访问他就知道他是不是凶手，那么这样的话就是：I. 他是一个真·孤立的点 II. 他在图里但是在他的强联通分量里只有他一个而且他能到达的所有点都能被其他入度为零的点所达到，这个细节70分.......

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdlib>

#define N 100010

#define M 300010

using namespace std;

inline int read()

{

   int sum=;

   char ch=getchar();

   while(ch<''||ch>'')ch=getchar();

   while(ch>=''&&ch<='')

   {

      sum=(sum<<)+(sum<<)+ch-'';

      ch=getchar();

   }

   return sum;

}

struct VIA

{

   int to,next;

}c[M];

struct Via

{

   int to,next,w;

}C[M<<];

int head[N],t,Head[N],T;

int dfn[N],low[N],stack[N],top;

inline void add(int x,int y)

{

   c[++t].to=y;

   c[t].next=head[x];

   head[x]=t;

}

inline void Add(int x,int y,int z)

{

   C[++T].to=y;

   C[T].w=z;

   C[T].next=Head[x];

   Head[x]=T;

}

inline int Min(int x,int y)

{

   return x<y?x:y;

}

int n,m,Ti,num,belong[N];

bool in[N];

bool special[N];

void Tarjan(int x)

{

    in[x]=;

    stack[++top]=x;

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

    for(int i=head[x];i;i=c[i].next)

    if(!dfn[c[i].to])

    {

      Tarjan(c[i].to);

      low[x]=Min(low[x],low[c[i].to]);

    }

    else if(in[c[i].to])

      low[x]=Min(low[x],dfn[c[i].to]);

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

    {

      int j,i=;

      ++num;

      do

      {

        j=stack[top--];

        in[j]=;

        belong[j]=num;

        i++;

      }while(j!=x);

      if(i==)

       special[num]=;

    }

}

int In[N];

inline void Build_New()

{

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

      for(int i=head[x];i;i=c[i].next)

        if(belong[x]!=belong[c[i].to])

          ++In[belong[c[i].to]],Add(belong[x],belong[c[i].to],),Add(belong[c[i].to],belong[x],-);

}

inline void Init()

{

   n=read(),m=read();

   for(int i=,x,y;i<=m;i++)x=read(),y=read(),add(x,y);

}

int visit[N];

bool F(int x,int to)

{

   if(visit[x]==t)return ;

   if(In[x]==&&x!=to)return ;

   for(int i=Head[x];i;i=C[i].next)

   if(C[i].w==-)

    if(F(C[i].to,to))

     return ;

   return ;

}

inline int find()

{

   t=;

   for(int i=;i<=num;i++)

    if(In[i]==&&special[i])

    {

      if(Head[i]==)return ;

      bool ans=;

      for(int j=Head[i];j;j=C[j].next)

      if(C[j].w==)

      {

       ++t;

       ans&=F(C[j].to,i);

      }

      if(ans)return ;

    }

   return ;

}

inline void work()

{

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

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

   Build_New();

   int get=;

   for(int i=;i<=num;i++)if(!In[i])get++;

   get=n-get;

   get+=find();

   double ans=(double)get/n;

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

}

int main()

{

   Init();

   work();

   return ;

}

巴特西

[BZOJ 2438] [中山市选2011]杀人游戏 Tarjan缩点

最新文章

热门文章