志愿者招募
链接：
题目大意：
第 (i) 天要 (a_i) 个人。第 (j) 种人从第 (s_j) 天干到第 (t_j) 天，要花 (c_j) 元。
找到一种方案使得付出的钱最少。
正文：
这是一种线性规划类问题，最小化 (sum_{i=1}^m x_ic_i)，且满足：
[left{egin{matrix}
sum_{i=1}^m [s_ileq1leq t_i]x_i &geq a_1 \
sum_{i=1}^m [s_ileq2leq t_i]x_i &geq a_2 \
vdots
end{matrix}
ight.]
考虑用费用流。在用费用流解决某线性规划类的问题时，可以考虑把约束条件的每行看作一点（本题为第 (i) 天），建立 (n+1) 个点，那么假设有边 ((u,v))。则表示已解决 (v-1) 个约束条件，现在要处理第 (v) 个。
考虑建模：
- (S) 连向 (1)、(n+1) 连向 (T)，流量是 (+infty)，费用 (0)。
- (i) 连向 (i+1)，流量是 (+infty-a_i)，费用 (0)。
- (s_i) 连向 (t_i+1)，流量 (+infty)，费用 (c_i)。
那么最大流一定是 (+infty)，否则无解。
代码：
const int N = 1010, M = 10010;
const ll inf = 1e18;
inline ll Read()
{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int n, m, s, t;
struct edge
{
ll to, w, val, nxt;
}e[(N + M) << 1];
int head[N], tot = 1;
void add(int u, int v, ll w, ll val)
{
e[++tot] = (edge) {v, w, val, head[u]}, head[u] = tot;
e[++tot] = (edge) {u, 0, -val, head[v]}, head[v] = tot;
}
int pre[N];
bool vis[N];
ll dis[N], incf[N];
queue <int> q;
bool SPFA()
{
memset (dis, 0x3f3f3f3f, sizeof dis);
while (!q.empty()) q.pop();
q.push(s);
vis[s] = 1; dis[s] = 0; incf[s] = inf;
while (!q.empty())
{
int u = q.front(); q.pop();
vis[u] = 0;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (dis[v] > dis[u] + e[i].val && e[i].w)
{
dis[v] = dis[u] + e[i].val;
pre[v] = i, incf[v] = min(incf[u], e[i].w);
if (!vis[v]) vis[v] = 1, q.push(v);
}
}
}
return dis[t] < inf;
}
ll MCMF()
{
ll cost = 0;
while (SPFA())
{
int u = t; cost += dis[t] * incf[t];
for (; u != s; u = e[pre[u] ^ 1].to)
e[pre[u]].w -= incf[t],
e[pre[u] ^ 1].w += incf[t];
}
return cost;
}
int main()
{
n = Read(), m = Read(), s = n + 2, t = s + 1;
add(s, 1, inf, 0);
for (int i = 1; i <= n; i++)
{
ll val = Read();
add(i, i + 1, inf - val, 0);
}
for (int i = 1; i <= m; i++)
{
int u = Read(), v = Read(); ll w = Read();
add(u, v + 1, inf, w);
}
add(n + 1, t, inf, 0);
printf ("%lld
", MCMF());
return 0;
}