SRM430 Div1 Medium

500

最大の次数が３なので、ある頂点に関して状態を2ビットで表せる。
DP[4^20]

int m_dist(int x1, int y1, int x2, int y2)
{
  return abs(x1 - x2) + abs(y1 - y2);
}

inline
int mask(int node, int bit)
{
  node *= 2;
  return bit & (3 * (1 << node));
}

inline
int degree(int node, int bit)
{
  bit = mask(node, bit);
  return bit >> (node * 2);
}

inline
int add_edge(int a, int b, int bit)
{
  int da = degree(a, bit) + 1;
  int db = degree(b, bit) + 1;
  bit -= mask(a, bit);
  bit -= mask(b, bit);
  return bit + (da * (1 << (a * 2))) + (db * (1 << (b * 2)));
}

const int N = 10 + 1;
int g[N][N];

const int M = 1 << 21;
int dp[2][M];

class TwinTowns {
public:
  vector <int> optimalTwinTowns(vector <int> x, vector <int> y, int maxPartners, int minDistance)
  {
    const int size = x.size();
    for (int i = 0; i < size; ++i) {
      for (int j = 0; j < size; ++j) {
        g[i][j] = m_dist(x[i], y[i], x[j], y[j]);
      }
    }
    const int inf = 1 << 30;
    fill(&dp[0][0], &dp[2 - 1][M - 1] + 1, inf);
    dp[0][0] = 0;
    const int BIT = 1 << (size * 2);
    int next = 0, curr = 0;
    for (int i = 0; i < size; ++i) {
      for (int j = i + 1; j < size; ++j) {
        curr = next;
        next = (curr + 1) % 2;
        copy(&dp[curr][0], &dp[curr][M - 1], &dp[next][0]);
        for (int bit = 0; bit < BIT; ++bit) {
          if (inf <= dp[curr][bit]) continue;
          if (g[i][j] < minDistance) continue;
          if (maxPartners <= degree(i, bit)) continue;
          if (maxPartners <= degree(j, bit)) continue;
          int b = add_edge(i, j, bit);
          dp[next][b] = min(dp[next][b], dp[curr][bit] + g[i][j]);
        }
      }
    }
    int edge = 0;
    int cost = inf;
    for (int bit = 0; bit < BIT; ++bit) {
      if (dp[next][bit] == inf) continue;
      int sum = 0;
      for (int i = 0; i < size; ++i) {
        sum += degree(i, bit);
      }
      int deg = sum / 2;
      if (edge < deg) {
        edge = deg;
        cost = dp[next][bit];
      }
      else if (edge == deg) {
        cost = min(cost, dp[next][bit]);
      }
    }
    vector<int> ret(2, 0);
    ret[0] = edge;
    ret[1] = cost;
    return ret;
  }


};