hiho一下第268周《分数调查》题目分析

2
0

《分数调查》题目分析

本题是一道带权并查集的题目。

"X比Y分数高S分"这个关系是有传递性的,也就是说如果我们知道X和Y的关系,也知道Y和Z的关系,就能知道X和Z的关系。

所以我们可以用并查集维护已知分数关系的学生集合,即同一集合中两两学生之间都能知道分数关系。

同时在并查集的树结构中,如果从X到Y有一条边,那么我们维护这条边的权值等于X比Y高的分数。(有可能是负数)

初始时每个学生单独一个集合,有一条自己指向自己的边,权值是0。

当我们要处理"X比Y高S分"这条信息时,我们按如下步骤:

1) 利用并查集找到X和Y各自的代表元,以及他们分别高于各自代表元的分数。不妨设X的代表元是P,X比P高Dx分;Y的代表元是Q,Y比Q高Dy分。

2) 如果P=Q,说明X和Y已经在一个集合中,没有任何新信息,那么不用做任何处理。(数据保证没有矛盾)

3) 如果P!=Q,我们需要合并P和Q两个集合。这时我们要增加一条边,有可能是P指向Q,也有可能是Q指向P。(根据按秩合并的不同情况)

假设是P指向Q(Q指向P结果类似),我们需要确定这条边的权值。不妨设权值是W,那么有Dx+W = S+Dy,推出W = S + Dy - Dx。

当我们要处理询问时,只要找到X和Y的代表元P和Q。如果P!=Q输出-1,否则输出Dx-Dy。

当然我们在路径压缩时,也需要更新权值,不再赘述。

1 answer(s)

1

哪里导致MLE了,递归堆栈最深也就10**5啊

#include <bits/stdc++.h>
using namespace std;

#define fora(i, l, r) for (int i = (int)(l); i < (int)(r); ++i)
#define ford(i, r, l) for (int i = (int)(r); i >= (int)(l); --i)

constexpr int MOD = 1e9 + 7;
constexpr int INF = INT32_MAX;
constexpr int MAXN = 1e5 + 10;
constexpr double eps = 1e-8;

using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
using Vec = vector<int>;

template <class T> void Min(T &a, T b) {if (b < a) a = b;}
template <class T> void Max(T &a, T b) {if (b > a) a = b;}

ll N, M, K, T;
int diff[MAXN], grp[MAXN];
int X, Y;

void Init() {
  memset(diff, 0, sizeof(diff));
  memset(grp, 0, sizeof(grp));
}

int FindPa(int x) {
  if (grp[x] != 0) {
    int p = FindPa(grp[x]);
    diff[x] += diff[grp[x]];
    grp[x] = p;
    return p;
  } else {
    return x;
  }
}

void Join(int u, int v, int w) {
  int x = FindPa(u);
  int y = FindPa(v);
  int a = diff[u], b = diff[v];
  grp[x] = y;
  diff[x] = b - a + w;
}

ll Solution() {
  int g0 = FindPa(X), g1 = FindPa(Y);
  if (g0 != g1)
    return -1;
  return diff[X] - diff[Y];
}

int main() {
#ifdef MY_DEBUG
  freopen("../in.txt", "r", stdin);
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);
  while (cin >> N >> M >> T) {
    Init();
    int u, v, w;
    while (M--) {
      cin >> u >> v >> w;
      Join(u, v, w);
    }
    while (T--) {
      cin >> X >> Y;
      cout << Solution() << '\n';
    }
  }
  return 0;
}

write answer 切换为英文 切换为中文


转发分享