求助,只有第26个点wa掉了
查看原帖
求助,只有第26个点wa掉了
385781
guanjinquan楼主2022/5/19 21:16

看起来是代码的某一处细节错了,但是找不到(x

有好心人愿意提供一组数据吗。

#include <bits/stdc++.h>
using namespace std;
#define ios_fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
#define emp emplace_back
const int maxn = 20000 + 7;

int n, m, G[5001][5001], scctot, cnt[maxn], sum;
int dfn[maxn], low[maxn], dfnnum;
int stk[maxn], top, ins[maxn], id[maxn];
vector<vector<int>> e;

void tarjan(int x) {
  dfn[x] = low[x] = ++dfnnum;
  ins[x] = 1, stk[++top] = x;
  for (int& v : e[x]) {
    if (!dfn[v]) {
      tarjan(v), low[x] = min(low[x], low[v]);
    } else if (ins[v]) {
      low[x] = min(low[x], dfn[v]);
    }
  }
  if (low[x] == dfn[x]) {
    ++scctot;
    for (int i = -1; i != x;) {
      i = stk[top--];
      ins[i] = false, id[i] = scctot;
    }
  }
}

void solve() {
  cin >> n;
  e.assign(2 * n + 1, {});
  for (int i = 1, tm; i <= n; i++) {
    cin >> tm;
    for (int j = 1, k; j <= tm; j++) {
      cin >> k, G[i][k] = 1;
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (i == j) continue;
      if (G[i][j]) {
        e[i + n].emp(j);  // 如果i不在团里面,j只能在团里面
      } else {
        e[i].emp(j + n);  // 如果i在团里面,j不可以在团里面
      }
    }
  }
  for (int i = 1; i <= 2 * n; i++)
    if (!dfn[i]) tarjan(i);
  for (int i = 1; i <= n; i++)
    if (id[i] == id[i + n]) {
      cout << 0 << endl;
      return;
    }
  int cnt0 = 0, cnt1 = 0;             // 独立集, 团
#define state(x) (id[x] > id[x + n])  // 1表示独立集
  for (int i = 1; i <= n; i++) {
    state(i) ? cnt0++ : cnt1++;
  }
  for (int i = 1; i <= n; i++) {
    if (state(i)) continue;
    for (int j = 1; j <= n; j++) {
      if (G[i][j]) cnt[j]++;
    }
  }
  for (int i = 1; i <= n; i++)
    if (cnt[i] == cnt1 - 1 && state(i)) sum++;
  int ans = (cnt0 >= 1) && (cnt1 >= 1);
  for (int i = 1; i <= n; i++) {
    if (state(i)) continue;
    int tmp = 0, pos = -1;
    for (int j = 1; j <= n; j++) {
      if ((state(j) == 1) && (G[i][j])) tmp++, pos = j;
    }
    if (tmp > 1) continue;
    if (tmp == 1) {
      ans += (pos > 0 && cnt[pos] == cnt1);  // 只能交换
    } else {
      ans += cnt1 > 1;  // 直接移过去
      for (int j = 1; j <= n; j++)
        if (state(j) && G[i][j]) {
          if (cnt[j] == cnt1 - 1) sum--;
          cnt[j]--;
          if (cnt[j] == cnt1 - 1) sum++;
        }
      ans += sum;  // 交换
      for (int j = 1; j <= n; j++)
        if (state(j) && G[i][j]) {
          if (cnt[j] == cnt1 - 1) sum--;
          cnt[j]++;
          if (cnt[j] == cnt1 - 1) sum++;
        }
    }
  }
  cout << ans << endl;
}

int main() {
  ios_fast;
  int TEST = 1;
  while (TEST--) solve();
}

/*


 */
2022/5/19 21:16
加载中...