比较好的图论
[cpp] // BEGIN CUT HERE // END CUT HERE #line 5 "MonsterFarm.cpp" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; class MonsterFarm { public: int numMonsters(vector 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 len=transforms[i].size(); int tem=0; for(j=0;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 for(i=0;i for(j=0;j path[i][j]=(path[i][j] || (path[i][k] && path[k][j])); for(i=0;i if(d[i]>=2 && path[0][i] && path[i][i]) return -1; ll num[2][51]; int cur=0; for(i=0;i num[cur][i]=0; num[cur][0]=1; for(i=0;i cur^=1; for(j=0;j for(j=0;j for(k=0;k num[cur][k]=(num[cur][k]+num[cur^1][j]*g[j][k])%Mod; } ll ans=0; for(i=0;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 string print_array(const vector &V) { ostringstream os; os << "{ "; for (typename vector::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 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 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 Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 1; verify_case(2, Arg1, numMonsters(Arg0)); } void test_case_3() { string Arr0[] = {"1", "3 4", "2", "2"}; vector Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 1; verify_case(3, Arg1, numMonsters(Arg0)); } void test_case_4() { string Arr0[] = {"2 2", "3", "4 4 4", "5", "6", "7 7 7 7", "7"}; vector Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 24; verify_case(4, Arg1, numMonsters(Arg0)); } void test_case_5() { string Arr0[] = {"2 3","5 7","2 4","5","6","4","7"}; vector Arg0(Arr0, Arr0 + (sizeof(Arr0