NOI2008 志愿者招募

题目:

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

思路:

  第 天的志愿者肯定是在第 天或第 天以前招募的,也就是说如果第 天志愿者不够,那么就要去前面找志愿者。而每一类招募就可以看作用 的代价,让 区间内的需求都减 。所以可以记录每天和上一天志愿者的需求差,然后用差分的方式处理招募。
  用一个单位流量表示一个志愿者需求,那么连边如下:
  对于每一个点,设
  如果 ,连边
  如果 ,连边
  对于每一类志愿者:
  连边
  然后跑费用流即可。

代码:

#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;

const int N = 1005, M = N * 6 + 20000;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k(G.HEAD[o]); k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void clear() {mset(HEAD, 0); tot = 0;}
    void add(int x, T w) { NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w; }
    T& operator[] (int x) { return W[x]; }
};

struct Edge {
    int to, flow, cost;
};
Link<N, M, Edge> G;
inline int rev(int k) {
    return ((k - 1) ^ 1) + 1;
}
void addEdge(int u, int v, int d, int c) {
    // printf("%d %d (%d,%d)\n", u, v, d, c);
    G.add(u, (Edge) {v, d, c}); 
    G.add(v, (Edge) {u, 0, -c});
}

struct Queue {
    int q[N], hed, tai;
    bool empty() {return hed == tai;}
    void push(int x) {q[tai++] = x; if(tai == N) tai = 0;}
    int pop() {int a = q[hed++]; if(hed == N) hed = 0; return a;}
} que;

int dis[N];
bool inq[N];
int spfa(int s, int t) {
    inq[s] = true; que.push(s);
    mset(dis, 63); dis[s] = 0;
    while(!que.empty()) {
        int o = que.pop(); inq[o] = false;
        erep(k, G, o) {
            Edge e = G[k];
            if(e.flow != 0 && tomin(dis[e.to], dis[o] + e.cost) && !inq[e.to]) {
                que.push(e.to); inq[e.to] = true;
            }
        }
    }
    return dis[t];
}
bool vis[N];
int dfs(int o, int mn, int t) {
    vis[o] = true;
    if(o == t) return mn;
    int ans = 0;
    erep(k, G, o) {
        Edge e = G[k];
        if(vis[e.to] || dis[e.to] != dis[o] + e.cost || e.flow == 0) continue;
        int tmp = dfs(e.to, min(e.flow, mn), t);
        G[k].flow -= tmp; mn -= tmp;
        G[rev(k)].flow += tmp; ans += tmp;
        if(mn == 0) break;
    }
    return ans;
}
int mcmf(int s, int t) {
    int c, d, ans = 0;
    while((c = spfa(s, t)) < 1e9) {
        do {
            mset(vis, 0);
            d = dfs(s, 1e9, t);
            ans += d * c;
        } while(vis[t]);
    }
    return ans;
}

int d[N];
int main() {
    // freopen("data.in", "r", stdin);
    int n, m;
    scanf("%d%d", &n, &m);
    rep(i, 1, n) scanf("%d", &d[i]);
    drep(i, ++n, 1) d[i] -= d[i - 1];
    int s = n + 1, t = s + 1;
    rep(i, 1, n) {
        if(d[i] > 0) addEdge(s, i, d[i], 0);
        if(d[i] < 0) addEdge(i, t, -d[i], 0);
    }
    rep(i, 1, n - 1) addEdge(i + 1, i, 1e9, 0);
    rep(i, 1, m) {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        addEdge(l, r + 1, 1e9, c);
    }
    printf("%d\n", mcmf(s, t));
    return 0;
}