我用如下方法建的图:

因为每个人必须打n-1场, 所以根据每个人最后的得分以及小Ho已经看过的比赛可以得出每一个选手还要赢几场以及还要输几场.

把每个选手拆成两个点, 假设选手id为i, 那么左边的点为i, 与源点s相连, 每条边的容量为还要赢的场数, 费用为0; 右边的点为i + n, 与汇点t相连, 每条边的容量为还要输的场数, 费用为0.

中间的边, 假设选手 i 与选手j (i != j)小Ho还没看到他们打过(就是(i, j) 而且(j, i)没出现过), 那么就建两条边, 一条 i 到j + n, 容量为1, 费用为B[i][j], 另一条 j 到 i + n, 容量为1, 费用为B[j][i]; 假设小Ho已经看他们打过了, 那么就不用建边, 并根据胜负关系把B[i][j或者B[j][i]加到最后的Ans里.

然后对图跑一遍最大费用最大流, 加上之前的Ans就是最后的答案.

然而一直WA. 请问这种方法错在哪里?

代码如下:

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x7f7f7f7f;
const int N = 105;
const int M = N * N * 10;

struct Edge {
  int u, v, cap, c, nxt;

  Edge() {}
  Edge(const int& _u, const int& _v, const int& _cap, const int& _c, const int& _nxt) : u(_u), v(_v), cap(_cap), c(_c), nxt(_nxt) {}
} es[M];

int head[N + N], tot;

int n, k;
bool vis[N][N];
int sc[N], battle[N], B[N][N];
int dp[N + N], from[N + N];

void addEdge(const int& u, const int& v, const int& cap, const int& c) {
  es[tot] = Edge(u, v, cap, c, head[u]);
  head[u] = tot++;
}

void addDoubleEdge(const int& u, const int& v, const int& cap, const int& c) {
  addEdge(u, v, cap, c);
  addEdge(v, u, 0, -c);
}

int spfa(const int &s, const int &t) {
  deque <int> de;
  for (int i = s; i <= t; ++i)
    dp[i] = -INF;
  dp[s] = 0;
  de.push_back(s);
  while (!de.empty()) {
    int u = de.front();
    de.pop_front();
    for (int i = head[u]; i != -1; i = es[i].nxt) {
      if (es[i].cap == 0)
        continue;
      int v = es[i].v;
      if (dp[u] + es[i].c > dp[v]) {
        dp[v] = dp[u] + es[i].c;
        from[v] = i;
        de.push_back(v);
      }
    }
  }
  if (dp[t] == -INF)
    return -INF;
  int temp = t, ret = 0;
  while (temp != s) {
    int id = from[temp];
    es[id].cap -= 1;
    es[id ^ 1].cap += 1;
    ret += es[id].c;
    temp = es[id].u;
  }
  return ret;
}

int mfmc(const int& s, const int &t) {
  int ret = 0;
  while (true) {
    int temp = spfa(s, t);
    if (temp == -INF)
      break;
    ret += temp;
  }
  return ret;
}

int main()
{
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i)
    scanf("%d", &sc[i]);
  scanf("%d", &k);
  for (int i = 0; i < k; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    ++battle[a]; ++battle[b];
    --sc[a];
    vis[a][b] = true;
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      scanf("%d", &B[i][j]);
  int s = 0, t = n + n + 1;
  memset(head, -1, sizeof(head));
  tot = 0;
  for (int i = 1; i <= n; ++i) {
    if (sc[i] != 0)
      addDoubleEdge(s, i, sc[i], 0);
    if (n - 1 - battle[i] - sc[i] != 0)
      addDoubleEdge(i + n, t, n - 1 - battle[i] - sc[i], 0);
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      if (vis[i][j] || vis[j][i])
        ans += vis[i][j] ? B[i][j] : B[j][i];
      else {
        addDoubleEdge(i, j + n, 1, B[i][j]);
        addDoubleEdge(j, i + n, 1, B[j][i]);
      }
    }
  }
  printf("%d\n", mfmc(s, t) + ans);
  return 0;
}