BZOJ2438: [中山市选2011]杀人游戏

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2438

Solution

毛看看肯定是要缩点的，缩点后统计入读为零的点的个数。
但是还有特殊情况，就是如果你确定了n-1个人的身份后最后一个人的身份是不需要问的，
所以如果存在单独一个点或一个入度为零但他连出去的点均能被其他点到达的点，那么答案-1。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll int
#define N 100005
#define M 600005
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    while (ch>'9'||ch<'0'){if (ch=='-') f=-1; ch=getchar();}
    while (ch<='9'&&ch>='0'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
struct edge{
    ll to,next;
}e[M],E[M];
ll n,m,cnt,top,dfn_num,color,ans;
ll head[N],dfn[N],stack[N],low[N],flag[N],indeg[N],Head[N],belong[N],vis[N],size[N];
void add(ll u,ll v){
    e[++cnt]=(edge){v,head[u]}; head[u]=cnt;
}
void insert(ll u,ll v){
    E[++cnt]=(edge){v,Head[u]}; Head[u]=cnt; indeg[v]++;
}
void tarjan(ll u){
    dfn[u]=low[u]=++dfn_num;
    flag[u]=1; stack[++top]=u;
    for (ll i=head[u],v=e[i].to;i;i=e[i].next,v=e[i].to)
        if (!dfn[v]) {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if (flag[v]) low[u]=min(low[u],dfn[v]);
    if (low[u]==dfn[u]){
        ll k; color++;
        do{
            k=stack[top--];
            belong[k]=color;
            flag[k]=0; size[color]++;
        }while (k!=u);
    }
}
void rebuild(){
    cnt=0;
    for (ll u=1;u<=n;u++){
        for (ll i=head[u],v=e[i].to;i;i=e[i].next,v=e[i].to)
            if (belong[u]!=belong[v]&&!vis[v]){
                insert(belong[u],belong[v]);
                vis[v]=1;
            } 
        for (ll i=head[u],v=e[i].to;i;i=e[i].next,v=e[i].to)
            if (belong[u]!=belong[v]) vis[v]=0;
    }
}
ll judge(ll x){
    if (indeg[x]||size[x]!=1) return 0;
    for (ll i=Head[x],v=E[i].to;i;i=E[i].next,v=E[i].to)
        if (indeg[v]==1) return 0;
    return 1;
}
int main(){
    n=read(); m=read();
    for (ll i=1;i<=m;i++){
        ll u=read(),v=read();
        add(u,v);
    }
    for (ll i=1;i<=n;i++)
        if (!dfn[i]) tarjan(i);
    rebuild();
    for (ll i=1;i<=color;i++)
        if (!indeg[i]) ans++;
    for (ll i=1;i<=color;i++)
        if (judge(i)) { ans--; break; }
    printf("%.6lf",(double)(n-ans)/n);
}