SRM 350 Div1 Medium StarsInGraphs

問題

やりかた

問題では頂点から出ている辺が3本以上の時を星として数えているが、2本の時、1本の時、0本の時もそれらを星と認めると、出次数がnの頂点で構成される星の総数はになる。このうち2本の星と1本の星と0本の星の総数はになるので2^nからこれらの数を引いたものが題意の星の数になる。
おのおのの頂点について出次数を数え、そこから構成される星の数を上の式から前計算する。あとは題意を満たす最長パスを、始点を変えながら深さ優先探索＋メモ化で計算してみればいい。一つでもパスがループする際には無限長のパスが出来てしまうので答えは-1。

以下ソース。

class StarsInGraphs {
public:
  int N, LIM;
  int num[50], dp[50];
  vector<string> e;

  ll calc(int d){
    return (1LL << d) - d * (d - 1) / 2 - d - 1;
  }
  
  int rec(int idx, vector<bool> vis){
    vis[idx] = true;
    
    if(count(ALL(vis), true) == N) return 0;
    if(dp[idx] != -1) return dp[idx];

    int ret = 0;
    for(int i = 0; i < N; i++){
      if(e[idx][i] == '1' && num[idx] <= num[i] && num[i] <= LIM){
	if(vis[i]) ret = INF;
	else ret = max(ret, rec(i, vis) + 1);
      }
    }
    return dp[idx] = ret;
  }
  int starryPaths(vector <string> adjacencyMatrix, int C) {
    N = adjacencyMatrix.size();
    e = adjacencyMatrix;
    LIM = C;
    fill(num, num + 50, 0);
    fill(dp, dp + 50, -1);
    for(int i = 0; i < N; i++) num[i] = calc(count(ALL(e[i]), '1'));

    int ans = 0;
    for(int i = 0; i < N; i++)
      if(0 < num[i] && num[i] <= C)
	ans = max(ans, 1 + rec(i, vector<bool>(N, false)));
    
    return ans >= INF ? -1 : ans;
  }
};

もちろん幅優先探索でも。それ以外でも。