好有意思的题呢qwq

首先观察到一点，我们可以把所有装置按照\(a_i\)的奇偶性进行分类（也可以说是黑白染色？）。容易发现任意偶数的最大公约数都至少是2，所以任意偶数间不会互相冲突。然后任意两个奇数的平方和一定不是完全平方数，可以这么证一下（感谢金爷！）：

那两个奇数可以分别设成\(2x + 1\)和\(2y + 1\)，然后他们的平方和就是\(4(x^2 + y^2 + x + y) + 2\)。然后思考一点，就是一个奇数的平方一定是奇数，所以说那个平方和是一个偶数。但是，如果一个完全平方数是偶数，那么它的算术平方根一定是偶数。然而，一个偶数的平方一定是4的倍数。但我们求出的平方和膜4得2，所以不行。

所以说冲突只存在于奇偶性不同的数中。然后用无限大的边来表示冲突关系，最小割高一波即可。

代码（常数卡卡卡……只能用pb_ds的蛤希表了）：

/**************************************************************
	Problem: 3158
	User: danihao123
	Language: C++
	Result: Accepted
	Time:9676 ms
	Memory:130460 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
typedef long long ll;
ll gcd(ll a, ll b) {
  if(!b) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}
__gnu_pbds::gp_hash_table<ll, bool> S2;
void process_S2() {
  for(ll i = 1LL; i * i <= 2000000000000LL; i ++) {
    S2[i * i] = true;
  }
}


const int maxno = 1050;
const int maxm = 2000500;
int first[maxno];
int next[maxm], to[maxm], cap[maxm], flow[maxm];
int gcnt = 0;
void add_edge(int u, int v, int f) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  to[gcnt] = v;
  cap[gcnt] = f;
  flow[gcnt] = 0;
}
int rev(int i) {
  if(1 & i) {
    return i + 1;
  } else {
    return i - 1;
  }
}
void ins_edge(int u, int v, int f) {
  add_edge(u, v, f); add_edge(v, u, 0);
}

int n;
int s, t;
int d[maxno];
bool bfs() {
  static bool vis[maxno];
  memset(vis, 0, sizeof(vis));
  d[s] = 1; vis[s] = true;
  std::queue<int> Q; Q.push(s);
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(cap[i] > flow[i] && !vis[v]) {
        d[v] = d[u] + 1; vis[v] = true;
        Q.push(v);
      }
    }
  }
  return vis[t];
}
int cur[maxno];
int dfs(int u, int a) {
  if(a == 0 || u == t) return a;
  int fl = 0;
  for(int &i = cur[u]; i; i = next[i]) {
    int v = to[i]; int f;
    if(d[v] == d[u] + 1 && (f = dfs(v, std::min(cap[i] - flow[i], a))) > 0) {
      fl += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[u] = -1;
  return fl;
}
int tot;
int dinic() {
  int ans = 0;
  while(bfs()) {
    for(int i = 0; i <= tot; i ++) cur[i] = first[i];
    ans += dfs(s, 0x7fffffff);
  }
  return ans;
}

const int maxn = 1005;
ll A[maxn]; int B[maxn];
int main() {
  process_S2();
  scanf("%d", &n); tot = n + 1;
  s = 0, t = tot;
  std::vector<int> odd, even;
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &A[i]);
    if(1LL & A[i]) {
      odd.push_back(i);
    } else {
      even.push_back(i);
    }
  }
  int ans = 0;
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &B[i]); ans += B[i];
    if(1LL & A[i]) {
      ins_edge(i, t, B[i]);
    } else {
      ins_edge(s, i, B[i]);
    }
  }
  for(int i = 0; i < even.size(); i ++) {
    int p1 = even[i];
    for(int j = 0; j < odd.size(); j ++) {
      int p2 = odd[j];
      if(gcd(A[p1], A[p2]) == 1LL && S2.find(A[p1] * A[p1] + A[p2] * A[p2]) != S2.end()) {
        ins_edge(p1, p2, 0x7f7f7f7f);
      }
    }
  }
  ans -= dinic();
  printf("%d\n", ans);
  return 0;
}

• 相关文章
• 全局相关文章