Luogu P3980 [NOI2008]志愿者招募

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

别人家的建图~~~~
好神奇
很容易想到志愿者的起始时间和终止时间连边，费用就是他的费用
但是每个点还有一个人数限制
必须要有那么多个人
也就是那么大的流量流过这个点
网上普遍的做法是
起点S为0号点，终点为n+2号点
S向1号点连容量inf，费用0的边
n+1号点向T连容量inf，费用为0的边
对于每个志愿者就那样连
从S连到T+1，容量inf，费用为C
对于人数限制
让每个i号点向i+1号点连边，容量inf-限制，费用为0
这样的意思就是
你一定要把减去的限制流满
也就满足了题目要求
因为初始的流量为inf
到了这里就要分流
人不够的就只能走带权边

#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, f, w;
}e[A];
int head[A], num = -1;
void add(int fr, int to, int f, int w) {
  e[++num].next = head[fr];
  e[num].to = to;
  e[num].f = f;
  e[num].w = w;
  head[fr] = num;
}
int dep[A], vis[A], n, m, S, T, pre[A], dis[A], last[A], f[A], a, b, c;
bool spfa() {
  memset(dis, 0x3f, sizeof dis);
  memset(f, 0x3f, sizeof f);
  memset(vis, 0, sizeof vis);
  queue<int> q; q.push(S); 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;
        f[ca] = min(f[fr], e[i].f);
        if (!vis[ca]) {
          vis[ca] = 1;
          q.push(ca);
        }
      }
    }
  }
  return pre[T] != -1;
}
int EK(int ans = 0) {
  while (spfa()) {
    int fr = T;
    ans += f[T] * dis[T];
    while (fr != S) {
      e[last[fr]].f -= f[T];
      e[last[fr] ^ 1].f += f[T];
      fr = pre[fr];
    }
  }
  return ans;
}

int main(int argc, char const *argv[]) {
  memset(head, -1, sizeof head);
  cin >> n >> m; S = 0; T = n + 2;
  add(S, 1, inf, 0); add(1, S, 0, 0);
  add(n + 1, T, inf, 0); add(T, n + 1, 0, 0);
  for (int i = 1; i <= n; i++) {
    cin >> a;
    add(i, i + 1, inf - a, 0);
    add(i + 1, i, 0, 0);
  }
  for (int i = 1; i <= m; i++) {
    cin >> a >> b >> c;
    add(a, b + 1, inf, c);
    add(b + 1, a, 0, -c);
  }
  cout << EK() << endl;
}