問題
http://community.topcoder.com/stat?c=problem_statement&pm=11232&rd=14724
各ノードごとに、次に変換するノードが与えられる。
次に変換するノードは１つ以上になる。
ノード０からスタートするとき、最後に収束するノード数を求める。
ただし、ノード数が発散するときはー１を返す。
解き方
グラフを利用する。
次に変換するノードが複数存在するので、
単純に連結しているかのグラフと次につながるエッジ数を表わす２つのグラフを利用する。
単純な連結グラフは発散するかの判定に用いワーシャルフロイドをかけて各ノード間の連結を確かめる。
自分から出るノードが２個以上かつループが存在するときに発散する。
次につながるエッジ数のグラフは答えを求めるのに用い、
ノード数分のステップを最低繰り返してノード数を収束させる。
答えは各ステップごとに各ノードの数を保存し、全回保存したノード数から足していき更新させればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class MonsterFarm {
public: int numMonsters(vector<string> transforms) {
int a[55][55]={},b[55][55]={};
int n=transforms.size(),MOD=1000000007;
FORE(i,0,n){
int x;
stringstream out(transforms[i]);
while(out>>x){
a[i][x-1]++;
b[i][x-1]=1;
}
}
FORE(k,0,n)FORE(i,0,n)FORE(j,0,n)if(b[i][k]&&b[k][j])b[i][j]=1;
FORE(i,0,n){
if(b[0][i]&&b[i][i]){
int sum=0;
FORE(j,0,n)sum+=a[i][j];
if(sum>1)return -1;
}
}
vector<int> vx(n,0);
vx[0]=1;
FORE(x,0,n){
vector<int> tmp(n,0);
FORE(i,0,n)FORE(j,0,n)tmp[j]=(tmp[j]+(long long)vx[i]*a[i][j])%MOD;
vx=tmp;
}
int ret=0;
FORE(i,0,n)ret=(ret+vx[i])%MOD;
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class MonsterFarm {
public: int numMonsters(vector<string> transforms) {
int a[55][55]={},b[55][55]={};
int n=transforms.size(),MOD=1000000007;
FORE(i,0,n){
int x;
stringstream out(transforms[i]);
while(out>>x){
a[i][x-1]++;
b[i][x-1]=1;
}
}
FORE(k,0,n)FORE(i,0,n)FORE(j,0,n)if(b[i][k]&&b[k][j])b[i][j]=1;
FORE(i,0,n){
if(b[0][i]&&b[i][i]){
int sum=0;
FORE(j,0,n)sum+=a[i][j];
if(sum>1)return -1;
}
}
vector<int> vx(n,0);
vx[0]=1;
FORE(x,0,n){
vector<int> tmp(n,0);
FORE(i,0,n)FORE(j,0,n)tmp[j]=(tmp[j]+(long long)vx[i]*a[i][j])%MOD;
vx=tmp;
}
int ret=0;
FORE(i,0,n)ret=(ret+vx[i])%MOD;
return ret;
}
};