这期讲的是网络流建图方法五—— 一对多问题，这类题呢，通常是一个决策影响多个决策比如洛谷P3980这道题，
题目描述
申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。
输入格式
第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负整数，表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了方便起见，我们可以认为每类志愿者的数量都是无限多的。
输出格式
仅包含一个整数，表示你所设计的最优方案的总费用。
输入
3 3
2 3 4
1 2 2
2 3 5
3 3 2
输出
10 14
---------------------------------------------------------------------------------------------------------------------------------------
对于这道题目，我们很容易想到对于志愿者（si, ti, ci）我们我们连接一条si——ti的边，容量为1，费用为ci，然后跑一遍费用流，但是你会发现这样建图有信息的缺失，我们没有办法去把每天至少ai人加入到这个图中，那么我们如何补全这个信息呢？仔细思考一下，我们可以把!@#@%$^&))))_+一时间不知道该怎么描述看图好了，这样我们跑一遍费用流就出来答案了，为什么呢因为要保证流量最大所以在第一个分支的时候会有两个流量被分到自愿者的边上这样我们就完成了对人数的限制。
---------------------------------------------------------------------------------------------------------------------------------------

AC代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

struct Edge
{
    int to, w, f, next;
}edg[MAXN];

int head[MAXN], dis[MAXN], flow[MAXN], pre[MAXN], last[MAXN], vis[MAXN];
int cnt = 0;

void init()
{
    memset(head, -1, sizeof(head));
    cnt = 0;
}

inline void add(int u, int v, int w, int f)
{
    edg[cnt].w = w;
    edg[cnt].to = v;
    edg[cnt].f = f;
    edg[cnt].next = head[u];
    head[u] = cnt++;
}

inline void Add_edge(int u, int v, int w, int f)
{
    add(u, v, w, f);
    add(v, u, 0, -f);
}

bool SPFA(int s, int t)
{
    queue<int> q;
    while(!q.empty()) q.pop();
    memset(dis, INF, sizeof(dis));
    memset(flow, INF, sizeof(flow));
    pre[t] = 0;
    dis[s] = 0;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        vis[u] = 0;
        for(int i = head[u]; i != -1; i = edg[i].next)
        {
            int v = edg[i].to;
            int w = edg[i].w;
            int newdis = dis[u] + edg[i].f;
            if(w && dis[v] > newdis)
            {
                dis[v] = newdis;
                flow[v] = min(flow[u], edg[i].w);
                pre[v] = u;
                last[v] = i;
                if(!vis[v])
                    q.push(v);
            }
        }
    }
    return pre[t];
}

int Mincost(int s, int t)
{
    int mincost = 0;
    while(SPFA(s, t))
    {
        mincost += dis[t] * flow[t];
        int now = t;
        while(now != s)
        {
            edg[last[now]].w -= flow[t];
            edg[last[now]^1].w += flow[t];
            now = pre[now];
        }
    }
    return mincost;
}

int main()
{
    int n, m, x, si, ti, ci;
    scanf("%d %d", &n, &m);
    init();
    int s = 0, t = n + 2;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &x);
        Add_edge(i, i + 1, INF - x, 0);
    }
    Add_edge(s, 1, INF, 0);
    Add_edge(n + 1, t, INF, 0);
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d %d %d", &si, &ti, &ci);
        Add_edge(si, ti + 1, INF, ci);
    }
    cout << Mincost(s, t) << endl;
}