题目

题解

很容易建立模型，如果两个点不能匹配，那么连一条边，那么问题就转化为了求一个图上的最大点权独立集。

而我们可以知道：

最大点权独立集+最小点权覆盖集=总权值。

同时最小点权覆盖在一般图上是np的，但是在二分图上就是可解的。

利用一系列数学性质，可以证明A[i]与A[j]奇偶性不同是ij之间连边的充分必要条件。

详细见lidaxin的博客

那么我们可以跑一边最大流即可。

代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int maxn = 1005;

const ll inf = 100000000000000;

ll N, A[maxn], B[maxn];

ll mx = 0;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

bool ok(ll a, ll b) {

  ll sq = a * a + b * b;

  ll t = sqrt(sq);

  if (sq != (t * t))

    return false;

  if (gcd(a, b) > 1)

    return false;

  return true;

}

struct edge {

  ll from;

  ll to;

  ll cap;

};

vector<edge> edges;

vector<int> G[maxn];

ll s, t, v, ans;

ll dist[maxn], iter[maxn];

void add_edge(int from, int to, ll cap) {

  edges.push_back((edge){from, to, cap});

  edges.push_back((edge){to, from, 0});

  int m = edges.size();

  G[from].push_back(m - 2);

  G[to].push_back(m - 1);

}

void bfs(int s) {

  memset(dist, -1, sizeof(dist));

  queue<int> q;

  q.push(s);

  dist[s] = 0;

  while (!q.empty()) {

    int u = q.front();

    q.pop();

    for (int i = 0; i < G[u].size(); i++) {

      edge &e = edges[G[u][i]];

      if (e.cap > 0 && dist[e.to] == -1) {

        dist[e.to] = dist[u] + e.cap;

        q.push(e.to);

      }

    }

  }

}

ll dfs(ll s, ll t, ll flow) {

  if (s == t)

    return flow;

  for (ll &i = iter[s]; i < G[s].size(); i++) {

    edge &e = edges[G[s][i]];

    if (e.cap > 0 && dist[e.to] > dist[s]) {

      ll d = dfs(e.to, t, min(flow, e.cap));

      if (d > 0) {

        e.cap -= d;

        edges[G[s][i] ^ 1].cap += d;

        return d;

      }

    }

  }

  return 0;

}

ll dinic(int s, int t) {

  ll flow = 0;

  while (1) {

    bfs(s);

    if (dist[t] == -1)

      return flow;

    memset(iter, 0, sizeof(iter));

    ll f;

    while ((f = dfs(s, t, inf)) > 0)

      flow += f;

  }

}

int main() {

  //  freopen("input.b", "r", stdin);

  ans = 0;

  scanf("%lld", &N);

  for (int i = 1; i <= N; i++) {

    scanf("%lld", &A[i]);

  }

  for (int i = 1; i <= N; i++) {

    scanf("%lld", &B[i]);

    ans += B[i];

  }

  // s:0, t:N+1

  s = 0, t = N + 1, v = t + 1;

  for (int i = 1; i <= N; i++) {

    if (A[i] & 1)

      add_edge(s, i, B[i]);

    else

      add_edge(i, t, B[i]);

    if (A[i] & 1)

      for (int j = 1; j <= N; j++) {

        if (!(A[j] & 1))

          if (ok(A[i], A[j]))

            add_edge(i, j, inf);

      }

  }

  ans -= dinic(s, t);

  printf("%lld", ans);

}

巴特西

[bzoj3158]千钧一发——二分图+网络流

题目

题解

代码

最新文章

热门文章