NOI2008 志愿者招募 （费用流）

题面

申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。

题解

写的真好

建模很巧妙

CODE

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cctype>

#include <cmath>

#include <queue>

using namespace std;

typedef long long LL;

template<class T>inline void read(T &x) {

	char ch; int flg = 1; while(!isdigit(ch=getchar()))if(ch=='-')flg=-flg;

	for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');x*=flg;

}

const int MAXN = 650;

const int MAXM = 50000;

const int inf = 1000000000;

int n, m;

int info[MAXN], fir[MAXN], to[MAXM<<1], nxt[MAXM<<1], c[MAXM<<1], wt[MAXM<<1], cnt = 1;

inline void link(int u, int v, int cc, int ww) {

	to[++cnt] = v; nxt[cnt] = fir[u]; fir[u] = cnt; c[cnt] = cc; wt[cnt] = ww;

	to[++cnt] = u; nxt[cnt] = fir[v]; fir[v] = cnt; c[cnt] = 0; wt[cnt] = -ww;

}

int S, T;

LL dis[MAXN], ans;

queue<int>q; bool vis[MAXN], inq[MAXN];

bool spfa() {

	memset(dis, 0x3f, sizeof dis);

	dis[S] = 0; q.push(S); inq[S] = 1;

	while(!q.empty()) {

		int u = q.front(); q.pop(); inq[u] = 0;

		for(int i = fir[u], v; i; i = nxt[i])

			if(c[i] && dis[v=to[i]] > dis[u] + wt[i]) {

				dis[v] = dis[u] + wt[i];

				if(!inq[v]) inq[v] = 1,	q.push(v);

			}

	}

	return dis[T] < dis[0];

}

int aug(int u, int Max) {

	if(u == T) {

		ans += Max*dis[T];

		return Max;

	}

	vis[u] = 1; int flow = 0, delta;

	for(int v, &i = info[u]; i; i = nxt[i])

		if(c[i] && !vis[v=to[i]] && dis[v] == dis[u] + wt[i] && (delta=aug(v, min(Max-flow, c[i])))) {

			c[i] -= delta, c[i^1] += delta, flow += delta;

			if(flow == Max) break;

		}

	vis[u] = 0; return flow;

}

LL Mincost(int s, int t) {

	S = s, T = t; ans = 0;

	while(spfa()) memcpy(info, fir, sizeof info), aug(S, inf);

	return ans;

}

int main () {

	read(n), read(m); int s = n+2, t = n+3;

	link(s, 1, inf, 0); link(n+1, t, inf, 0);

	for(int i = 1, x; i <= n; ++i) read(x), link(i, i+1, inf-x, 0);

	for(int i = 1, l, r, w; i <= m; ++i) read(l), read(r), read(w), link(l, r+1, inf, w);

	printf("%lld\n", Mincost(s, t));

}