SRM495 Div1 Medium(500) CarrotBoxes

CarrotBoxes

強連結成分分解して、他から情報が得られない成分のみ開ければ良い。そのような成分の個数をxとすると成功する確率は(N-x)/N。ただし、最後に回すことで箱が１つだけ残るような成分があれば、その箱を開けずとも空と分かるので、確率は(N-x+1)/N。

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

//  強連結成分分解
//  辺を受け取り、各ノードが属する成分を返す
vector<int>scc(vector<vector<bool> >E)
{
    int n=(int)E.size();
    vector<int>v1(n,-1),v2(n);
    //  帰りがけ順で番号付け
    for(int i=n,c=0;i--;)if(v1[i]<0){
        vector<int>p(1,i);
        while(!p.empty()){
            int t=p.back();
            v1[t]=0;
            for(int j=n;j--;)if(j!=t&&E[t][j]&&v1[j]<0)p.push_back(j);
            if(p.back()==t)p.pop_back(),v1[t]=c++;}}
    //  番号が最大のノードから到達可能な点を同じ成分に
    for(int c=0,m;m=max_element(&v1[0],&v1[0]+n)-&v1[0],v1[m]>=0;c++){
        vector<int>p(1,m);
        while(!p.empty()){
            int t=p.back();
            v1[t]=-1,v2[t]=c;
            for(int j=n;j--;)if(j!=t&&E[j][t]&&v1[j]>=0)p.push_back(j);
            if(p.back()==t)p.pop_back();}}
    return v2;
}

void dfs( vector<vector<bool> > E, vector<bool> *V, int p )
{
    (*V)[p] = true;
    for ( int i=0; i<(int)E.size(); i++ )
        if ( E[p][i] && ! (*V)[i] )
            dfs(E,V,i);
}

class CarrotBoxes{public:
double theProbability( vector <string> information )
{
    int n = (int)information.size();

    vector<vector<bool> > E(n,vector<bool>(n));
    for ( int i=0; i<n; i++ )
    for ( int j=0; j<n; j++ )
        E[i][j] = information[i][j] == 'Y';

    vector<int> v = scc(E);

    //  強連結成分のうち他の成分からの辺が無い成分を候補とする
    vector<int> cand;
    for ( int i=0; i<=*max_element(v.begin(),v.end()); i++ )
    {
        bool f = true;
        for ( int j=0; j<n; j++ )
        for ( int k=0; k<n; k++ )
            if ( v[j]!=i && v[k]==i && E[j][k] )
                f = false;
        if ( f )
            cand.push_back(i);
    }

    //  最後にしたときにその候補１つだけが残るような候補があるならば、
    //  その候補を最後にすることで確率が上がる
    for ( int i=0; i<(int)cand.size(); i++ )
    {
        vector<bool> t(n,false);

        for ( int j=0; j<(int)cand.size(); j++ )
        if ( j != i )
        {
            int k;
            for ( k=0; k<n; k++ )
                if ( v[k] == cand[j] )
                    break;
            dfs(E,&t,k);
        }

        if ( count(t.begin(),t.end(),false) == 1 )
            return (double)(n-cand.size()+1)/n;
    }

    return (double)(n-cand.size())/n;
}};