SRM 407 DIV1 Easy - CorporationSalary（復習○）

February 13, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=9824&rd=12179

部下とマネージャーからなるサラリーマンの会社がある。
配列が与えられ、ある人に対してその部下が誰かがわかっている。
また、ある人の部下の部下は、ある人の部下でもあり、
あるひとのマネージャーのマネージャーは、ある人のマネージャーでもある。

ここで、ある人の給料は、その人の部下の給料の合計になる。
部下がいないひとの給料は１になる。

このとき、その会社のサラリーマン全員の給料の合計を求める。

解き方

ある人の給料はその人の部下全員の給料の合計であるので、ＤＦＳにて答えを求めてあげればよい。

コード

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()

long long dp[60];
vector<string> R;

class CorporationSalary {

public:

long long f(int x){
if(dp[x]!=-1)return dp[x];
long long ret=0;
FORE(i,0,R.size())if(R[x][i]=='Y')ret+=f(i);
if(ret==0)ret=1;
return dp[x]=ret;
}

long long totalSalary(vector<string> relations) {
memset(dp,-1,sizeof(dp));
R=relations;

long long ret=0;
FORE(i,0,R.size())ret+=f(i);

return ret;
}

};

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 CorporationSalary {

public:

long long totalSalary(vector<string> relations) {
int n=relations.size();
vector<long long> vx(n,0);
int used[n];
memset(used,0,sizeof(used));

FORE(i,0,n){
int valid=1;
FORE(j,0,n)if(relations[i][j]=='Y')valid=0;
if(valid){
vx[i]=1;
used[i]=1;
}
}

while(accumulate(used,used+n,0)<n){
FORE(i,0,n)if(!used[i]){
int valid=1;
long long score=0;
FORE(j,0,n)if(relations[i][j]=='Y'){
if(!used[j])valid=0;
else score+=vx[j];
}
if(valid){
vx[i]=score;
used[i]=1;
}
}
}

long long ret=0;
FORE(i,0,n)ret+=vx[i];
return ret;
}

};

グラフ