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 A 1000010
#define B 2010

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;
}