問題
http://topcoder.bgcoder.com/print.php?id=2031
無向グラフが与えられる。
入力となるノード（人）を選んで噂を流したとき、そこからつながるノードへ噂を伝搬することができる。
このとき、全てのノードにいきわたったらそのうわさが全員に伝わったことになる。
一人に伝えられる噂はひとつであるとき、全員に伝えられる噂は最大何種類あるか求める。
解き方
入力となるノードの全ての選び方に対して、全員に伝わるかを判定する。
次に、ｄｐを用いて選んだノードを状態として持たせ、そこからＸＯＲにて部分集合の最大を求める。
ＸＯＲを求めるときはＸ＾Ｙが必ず部分集合となるように全ての値を検索するのがポイント。
コード
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 InformFriends {
public: int maximumGroups(vector<string> friends) {
int n=friends.size();
int ok[1<<16]={};
for(int i=0;i<(1<<n);i++){
int mask=i;
FORE(j,0,n)FORE(k,0,n)if((i&(1<<j))&&friends[j][k]=='Y')mask|=(1<<k);
ok[i]=(mask==(1<<n)-1);
}
int dp[1<<16]={};
for(int i=0;i<(1<<n);i++){
for(int j=i;j>0;j=(j-1)&i){
dp[i]=max(dp[i],dp[i^j]+ok[j]);
}
}
return dp[(1<<n)-1];
}
};
#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 InformFriends {
public: int maximumGroups(vector<string> friends) {
int n=friends.size();
int ok[1<<16]={};
for(int i=0;i<(1<<n);i++){
int mask=i;
FORE(j,0,n)FORE(k,0,n)if((i&(1<<j))&&friends[j][k]=='Y')mask|=(1<<k);
ok[i]=(mask==(1<<n)-1);
}
int dp[1<<16]={};
for(int i=0;i<(1<<n);i++){
for(int j=i;j>0;j=(j-1)&i){
dp[i]=max(dp[i],dp[i^j]+ok[j]);
}
}
return dp[(1<<n)-1];
}
};