SRM 531 div1 600

比较好的图论

[cpp]
// BEGIN CUT HERE

// END CUT HERE
#line 5 "MonsterFarm.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;

typedef long long ll;

class MonsterFarm
{
    public:
    int numMonsters(vector <string> transforms){
        const int Mod=1000000007;
        int g[51][51],d[51],path[51][51];
        int len,i,j,k;
        int n=transforms.size();
        memset(g,0,sizeof(g));
        memset(d,0,sizeof(d));
        memset(path,0,sizeof(path));
        for(i=0;i<n;i++){
            len=transforms[i].size();
            int tem=0;
            for(j=0;j<len;j++){
                if(transforms[i][j]==' '){
                    d[i]++;
                    g[i][tem-1]++;
                    path[i][tem-1]=1;
                    tem=0;
                    continue;
                }
                tem=tem*10+transforms[i][j]-'0';
            }
            d[i]++;
            g[i][tem-1]++;
            path[i][tem-1]=1;
        }
        for(k=0;k<n;k++)
            for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                    path[i][j]=(path[i][j] || (path[i][k] && path[k][j]));
        for(i=0;i<n;i++)
            if(d[i]>=2 && path[0][i] && path[i][i])
                return -1;

        ll num[2][51];
        int cur=0;
        for(i=0;i<n;i++)
            num[cur][i]=0;
        num[cur][0]=1;
        for(i=0;i<n;i++){
            cur^=1;
            for(j=0;j<n;j++)num[cur][j]=0;
            for(j=0;j<n;j++)
                for(k=0;k<n;k++)
                    num[cur][k]=(num[cur][k]+num[cur^1][j]*g[j][k])%Mod;
        }
        ll ans=0;
        for(i=0;i<n;i++)
            ans=(ans+num[cur][i])%Mod;
        return (int)ans;
    }

// BEGIN CUT HERE
    public:
    void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
    private:
    template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
    void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
    void test_case_0() { string Arr0[] = {"1"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 1; verify_case(0, Arg1, numMonsters(Arg0)); }
    void test_case_1() { string Arr0[] = {"1 1"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = -1; verify_case(1, Arg1, numMonsters(Arg0)); }
    void test_case_2() { string Arr0[] = {"2", "3", "1"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 1; verify_case(2, Arg1, numMonsters(A

补充：软件开发 , C++ ,