Wannafly & Comet OJ 夏季欢乐赛（2019）G-篮球校赛

题目链接：​​传送门​​

标题有点长

不过没关系

很一眼的费用流

比赛的时候加边有点小错误

又又又

然后三天后的现在才找到啊哈哈哈

差点疯辽

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
struct node {
  int next, to; ll w, f;
}e[A];
int head[B], num = 1;
void add(int fr, int to, ll w, ll f) {
  e[++num].next = head[fr]; e[num].to = to;
  e[num].w = w; e[num].f = f; head[fr] = num;
  swap(to, fr);
  e[++num].next = head[fr]; e[num].to = to;
  e[num].w = -w; e[num].f = 0; head[fr] = num;
}
int n, S, T, pre[B], last[B], vis[B];
ll dis[B], w, minn, flow[B];
queue<int> q;
bool SPFA() {
  memset(dis, 0x7f, sizeof dis);
  memset(flow, 0x7f, sizeof flow);
  memset(vis, 0, sizeof vis);
  q.push(S); vis[S] = 1; dis[S] = 0; pre[T] = -1;
  while (!q.empty()) {
    int fr = q.front(); q.pop(); vis[fr] = 0;
    for (int i = head[fr]; ~i; i = e[i].next) {
      int ca = e[i].to;
      if (e[i].f and dis[ca] > dis[fr] + e[i].w) {
        dis[ca] = dis[fr] + e[i].w;
        pre[ca] = fr; last[ca] = i;
        flow[ca] = min(flow[fr], e[i].f);
        if (!vis[ca]) {
          vis[ca] = 1;
          q.push(ca);
        }
      }
    }
  }
  return pre[T] != -1;
}
void EK() {
  while (SPFA()) {
    int fr = T;
    minn += flow[T] * dis[T];
    while (fr != S) {
      e[last[fr]].f -= flow[T];
      e[last[fr] ^ 1].f += flow[T];
      fr = pre[fr];
    }
  }
}

int main(int argc, char const *argv[]) {
  memset(head, -1, sizeof head);
  cin >> n; S = 0; T = n + 6;
  for (int i = 1; i <= 5; i++) add(n + i, T, 0, 1);
  for (int i = 1; i <= n; i++) {
    add(S, i, 0, 1);
    for (int j = 1; j <= 5; j++) {
      scanf("%lld", &w);
      add(i, n + j, -w, 1);
    }
  }
  EK(); cout << -minn << endl; return 0;
}