SRM583 Div1 Medium

500

グラフ中の最長パスを求める。もし両端を切り替える必要があるなら、そのパスで切り替える。
パスの両端の片方あるいは両方を木から取り除いて同様の操作を繰り返す。

もっと簡単にDFSやループだけで解けるらしい。

const int N = 50 + 2;

void rev(int i, int j, char color[N][N])
{
  color[i][j] = '0' + (color[i][j] == '0');
  color[j][i] = '0' + (color[j][i] == '0');
}

char colorA[N][N];
char colorB[N][N];

vector<int> g[N];
set<int> removed;

vector<int> bfs(const int V, int src = -1)
{
  for (int i = 0; src == -1 && i < V; ++i) {
    if (removed.count(i) == 0) src = i;
  }
  if (src == -1) return vector<int>();

  int dist[N];
  fill(dist, dist + N, 1 << 28);
  dist[src] = 0;

  int path[N];
  fill(path, path + N, -1);

  set<int> vis;
  vis.insert(src);

  queue<int> q;
  for (q.push(src); q.size(); q.pop()) {
    int curr = q.front();
    for (int i = 0; i < g[curr].size(); ++i) {
      int next = g[curr][i];
      if (!removed.count(next) && !vis.count(next)) {
        path[next] = curr;
        vis.insert(next);
        dist[next] = dist[curr] + 1;
        q.push(next);
      }
    }
  }

  int dst = src;
  for (int i = 0; i < N; ++i) {
    if (vis.count(i) && dist[dst] < dist[i]) dst = i;
  }

  vector<int> v;
  for (; dst != src; dst = path[dst]) {
    v.push_back(dst);
  }
  v.push_back(src);
  reverse(v.begin(), v.end());
  return v;
}

class TurnOnLamps {
public:
  int minimize(vector <int> R, string A, string B)
  {
    const int M = R.size();

    fill(g, g + N, vector<int>());
    removed.clear();

    for (int i = 0; i < M; ++i) {
      int j = i + 1;
      int k = R[i];
      colorA[j][k] = colorA[k][j] = A[i];
      colorB[j][k] = colorB[k][j] = B[i];
      g[j].push_back(k);
      g[k].push_back(j);
    }

    int ret = 0;
    for (int loop = M * 2; loop--; ) {
      vector<int> path = bfs(R.size());
      path = bfs(R.size(), path.size() ? path.back() : -1);
      if (path.size() == 2) {
        if (colorA[path[0]][path[1]] == '0' && colorB[path[0]][path[1]] == '1') {
          rev(path[0], path[1], colorA);
          ++ret;
        }
        removed.insert(path[0]);
        removed.insert(path[1]);
      } else if (2 < path.size()) {
        int a = path[0], b = path[1];
        int c = path[path.size() - 2], d = path[path.size() - 1];
        if (colorA[a][b] == '0' && colorB[a][b] == '1' &&
            colorA[c][d] == '0' && colorB[c][d] == '1') {
          for (int i = 0; i + 1 < path.size(); ++i) {
            rev(path[i], path[i + 1], colorA);
          }
          ++ret;
          removed.insert(path.front());
          removed.insert(path.back());
        } else if (colorA[a][b] == '0' && colorB[a][b] == '1') {
          removed.insert(path.back());
        } else if (colorA[c][d] == '0' && colorB[c][d] == '1') {
          removed.insert(path.front());
        } else {
          removed.insert(path.front());
          removed.insert(path.back());
        }
      }
    }
    return ret;
  }