当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

同时考虑点权和边权比较困难,如果可以把边权并到点权里,那么就可以直接贪心了。

注意到对于一条边的边权对答案的贡献

  • 如果两边都是黑点,对答案的贡献为 1 ,可以看做两个黑点分别为答案贡献了 \frac 1 2
  • 如果两边都是白点,对答案的贡献为 -1 ,可以看做两个白点分别为答案贡献了 - \frac 1 2
  • 如果一边是白点一边是黑点,贡献为 0 ,可以看做黑点为答案贡献了 \frac 1 2 的边权,白点为答案贡献了 - \frac 1 2 的贡献

这样话设置每个点的排序关键字为点权加上 \frac 1 2 的相邻边权和,按从大到小排序后奇数位为黑点,偶数位为白点即可。

// =================================
//   author: memset0
//   date: 2019.07.08 13:14:31
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define rep(i, l, r) for (int (i) = (l), __lim = (r); (i) <= __lim; (i)++)
#define for_each(i, a) for (size_t i = 0, __lim = a.size(); i < __lim; ++i)
namespace ringo {

template <class T> inline void read(T &x) {
  x = 0; char c = getchar(); bool f = 0;
  while (!isdigit(c)) f ^= c == '-', c = getchar();
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  if (f) x = -x;
}
template <class T> inline void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) print(x / 10);
  putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }
template <class T> inline void print(T a, int l, int r, std::string s = "") {
  if (s != "") std::cout << s << ": ";
  for (int i = l; i <= r; i++) print(a[i], " \n"[i == r]);
}

const int N = 1e5 + 10;
ll ans;
int n, m, id[N], key[N], val[N];

inline bool cmp(int x, int y) {
  return key[x] > key[y];
}

void main() {
  read(n), read(m);
  for (int i = 1; i <= n; i++) {
    read(val[i]);
    id[i] = i;
    key[i] = val[i] << 1;
  }
  for (int i = 1, u, v, w; i <= m; i++) {
    read(u), read(v), read(w);
    key[u] += w, key[v] += w;
  }
  std::sort(id + 1, id + n + 1, cmp);
  for (int i = 1; i <= n; i++) {
    ans += (i & 1 ? 1 : -1) * key[id[i]];
  }
  print(ans >> 1, '\n');
}

} signed main() {
#ifdef memset0
  freopen("1.in", "r", stdin);
#endif
  return ringo::main(), 0;
}

巧妙的思路 博弈 贪心 Favorite

洛谷4035 [JSOI2008]球形空间产生器
上一篇 «
LOJ6674 赛道修建
» 下一篇