题解 P6472 【[COCI2008-2009#6]SLICICE】

· · 题解

两张卡片分给两个小朋友，可以分成 (2, 0)，(1, 1) 和 (0, 2)，也就是每种分法都可以，没有限制。

就很适合网络流。

令 u_i, v_i 表示第 i 次记录中的两位小朋友，a_j 表示第 j 位小朋友手上卡片的数量。

从超级源 S 向每次记录 i 连容量为 2 的边。

每次记录 i 向对应的两位小朋友 u_i, v_i 各连一条容量为 + \infty 的边。

每位小朋友 j 向超级汇 T 连一条容量为 a_j 的边。

跑一遍最大流，我们就求出了一种满足条件的分配方案。

最后还有若干次被遗忘的记录，记第 j 位小朋友剩余卡片数为 b_j。显然 b_j 均为自然数。

若 b_j 为偶数，则可以不断抓一名小朋友和他一起买然后赢过对方拿到 2 张，直到到达数量为止。

若 b_j 为奇数，可以先和另一位 b 也为奇数的小朋友各拿 1 张变成偶数，然后按照上述方法处理。

于是答案就构造完毕了。

时间复杂度 \mathcal{O}((n + m) ^ 2)。

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

const int MaxN = 100, MaxM = 1000;
const int MaxV = 1102;
const int INF = 0x7F7F7F7F;

struct edge_t {
  int to, cap, rev;
  edge_t(int _to = 0, int _cap = 0, int _rev = 0) { to = _to, cap = _cap, rev = _rev; }
};

int N, M, K;
int A[MaxN + 5];
int U[MaxM + 5], V[MaxM + 5], W[MaxM + 5];
std::vector<edge_t> Gr[MaxV + 5];

void init() {
  scanf("%d %d", &N, &M);
  for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
  for (int i = 1; i <= M; ++i) scanf("%d %d", &U[i], &V[i]);
}

inline void addEdge(int from, int to, int cap) {
  Gr[from].push_back(edge_t(to, cap, (int) Gr[to].size()));
  Gr[to].push_back(edge_t(from, 0, (int) Gr[from].size() - 1));
}

namespace Dinic {

int Level[MaxV + 5], Iter[MaxV + 5];

void bfs(int s) {
  static int que[MaxV + 5];
  int head = 1, tail = 0;
  memset(Level, -1, sizeof Level);
  que[++tail] = s;
  Level[s] = 0;
  while (head <= tail) {
    int u = que[head++];
    for (int i = 0; i < (int) Gr[u].size(); ++i) {
      edge_t e = Gr[u][i];
      if (e.cap > 0 && Level[e.to] < 0) {
        Level[e.to] = Level[u] + 1;
        que[++tail] = e.to;
      }
    }
  }
}

int dfs(int u, int t, int f) {
  if (u == t) return f;
  for (int &i = Iter[u]; i < (int) Gr[u].size(); ++i) {
    edge_t &e = Gr[u][i];
    if (e.cap > 0 && Level[e.to] > Level[u]) {
      int d = dfs(e.to, t, std::min(f, e.cap));
      if (d > 0) {
        e.cap -= d;
        Gr[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

int maxFlow(int s, int t) {
  int flow = 0;
  for (;;) {
    bfs(s);
    if (Level[t] < 0) break;
    memset(Iter, 0, sizeof Iter);
    for (;;) {
      int f = dfs(s, t, INF);
      if (f == 0) break;
      flow += f;
    }
  }
  return flow;
}

}

void solve() {
  int Source = N + M + 1, Target = N + M + 2;
  for (int i = 1; i <= M; ++i) {
    addEdge(Source, i, 2);
    addEdge(i, U[i] + M, 2);
    addEdge(i, V[i] + M, 2);
  }
  for (int i = 1; i <= N; ++i)
    addEdge(i + M, Target, A[i]);
  Dinic::maxFlow(Source, Target);
  for (int i = 1; i <= M; ++i)
    for (int j = 0; j < (int) Gr[i].size(); ++j) {
      edge_t e = Gr[i][j];
      if (e.to == U[i] + M) W[i] = Gr[e.to][e.rev].cap;
    }
  static int b[MaxN + 5];
  for (int i = 1; i <= N; ++i)
    for (int j = 0; j < (int) Gr[i + M].size(); ++j) {
      edge_t e = Gr[i + M][j];
      if (e.to == Target) b[i] = e.cap;
    }
  K = M;
  for (int i = 1; i <= N; ++i) {
    while (b[i] > 1) {
      K++;
      U[K] = i, V[K] = 1 + (i == 1), W[K] = 2;
      b[i] -= 2;
    }
  }
  int lst1 = 0;
  for (int i = 1; i <= N; ++i) {
    if (b[i] == 0) continue;
    if (lst1 == 0) lst1 = i;
    else {
      K++;
      U[K] = lst1, V[K] = i, W[K] = 1;
      lst1 = 0;
    }
  }
  printf("%d\n", K);
  for (int i = 1; i <= K; ++i)
    printf("%d %d %d\n", U[i], V[i], W[i]);
}

int main() {
  init();
  solve();
  return 0;
}