40pts求助

P4171 [JSOI2010] 满汉全席

ChickyHas @ 2023-09-19 09:50:43

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int N = 201;

int t, n, m, dfn[N], low[N], s[N], top, cnt, res[N], idx;
vector<int> e[N];
string s1, s2;
bool b[N];

void Tarjan(int x) {
  dfn[x] = low[x] = ++idx;
  s[++top] = x, b[x] = 1;
  for (int i : e[x]) {
    if (!dfn[i]) {
      Tarjan(i);
      low[x] = min(low[x], low[i]);
    } else if (b[i]) {
      low[x] = min(low[x], dfn[i]);
    }
  }
  if (low[x] == dfn[x]) {
    ++cnt;
    while (s[top + 1] != x) {
      b[s[top]] = 0, res[s[top--]] = cnt;
    }
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> t;
  while (t--) {
    cin >> n >> m;
    top = cnt = idx = 0;
    for (int i = 1; i <= n << 1; ++i) {
      s[i] = dfn[i] = low[i] = b[i] = res[i] = 0;
      e[i].clear();
    }
    for (int i = 1; i <= m; ++i) {
      cin >> s1 >> s2;
      bool b1 = s1[0] == 'm', b2 = s2[0] == 'm';
      int x = 0, y = 0;
      for (int j = 1; j < s1.size(); ++j) {
        x = (x << 3) + (x << 1) + s1[j] - '0';
      }
      for (int j = 1; j < s2.size(); ++j) {
        y = (y << 3) + (y << 1) + s2[j] - '0';
      }
      if (b1 && b2) {
        e[x + n].emplace_back(y);
        e[y + n].emplace_back(x);
      } else if (!b1 && b2) {
        e[x].emplace_back(y);
        e[y + n].emplace_back(x + n);
      } else if (b1 && !b2) {
        e[x + n].emplace_back(y);
        e[y].emplace_back(x);
      } else {
        e[x].emplace_back(y + n);
        e[y].emplace_back(x + n);
      }
    }
    for (int i = 1; i <= n << 1; ++i) {
      if (!dfn[i]) {
        Tarjan(i);
      }
    }
    bool f = 1;
    for (int i = 1; i <= n; ++i) {
      if (res[i] == res[i + n]) {
        f = 0;
        break;
      }
    }
    cout << (f ? "GOOD\n" : "BAD\n");
  }
  return 0;
}

rt,不知道哪里错了


by ChickyHas @ 2023-09-19 09:57:30

md,建图建错了,真难绷


|