题目链接：ZOJ3229-Shoot the Bullet

题意：

一条舔狗给m个女神拍照，计划拍照n天，每天最多给C个女神拍照，拍照数不能超过D，而且给女神a拍照的数量有限制[La,Ra]，然后n天之内至少给女神a拍照G张，舔狗是否能完成任务，若能完成则输出每天给每个女神各拍了多少张照片，不能完成则输出-1。

题解：

典型的第二类有上下界的网络流模型。

S向每天连[0,day]的边，每一天与拍照的妹子连[l,r]的边，每个女孩和T连[g,inf]的边。

然后根据模型建图求解即可。

1. 先建立超级源点SS和超级汇点TT（原图中的源点汇点分别用S和T表示），对于原图中的边(u,v)，流量限制为[l,r]，实际建图时把该边的流量设为r-l。
2. 对于原图中的某一个点k，记deg[k]表示流入这个点所有边的流量下界和减去流出这个点的流量下界和的值。若deg[k]>0，连边(SS,k)，流量为deg[i]；若deg[k]<0，连边(k,TT)，流量为-deg[i]。
3. 在原图中连边(T,S)，容量为inf。
4. 然后判断新图中是否存在可行流。
5. 若存在，先删除(T,S)这条边，然后记flow_1=maxflow(T,S)，为此时(T,S)的最大流，即求反向边$(S,T)$的流量。然后在残余网络中求flow_2=maxflow(S,T)，最终答案即为(flow_1+flow_2)。

PS.注意因为最后需要输出边，所以注意建边顺序。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1500;
const int MAXM = 1e5;
const int inf = 0x3f3f3f3f;
int n, m, st, ed;
int day[MAXN], wom[MAXN];
int cnt, fir[MAXN], depth[MAXN], cur[MAXN], deg[MAXN], L[MAXM], R[MAXM];
struct node
{
    int v, w, nxt;
} edge[MAXM * 2];

void addedge(int u, int v, int w)
{
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = fir[u];
    fir[u] = cnt++;
}
int dfs(int u, int flow)
{
    if (u == ed)
        return flow;
    for (int &i = cur[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        int w = edge[i].w;
        if (depth[v] == depth[u] + 1 && w != 0)
        {
            int di = dfs(v, min(flow, w));
            if (di > 0)
            {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}
bool bfs()
{
    queue<int> q;
    while (!q.empty())
        q.pop();
    memset(depth, 0, sizeof(depth));
    depth[st] = 1;
    q.push(st);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if (depth[v] == 0 && w > 0)
            {
                depth[v] = depth[u] + 1;
                q.push(v);
            }
        }
    }
    if (depth[ed] > 0)
        return 1;
    else
        return 0;
}
int dinic(int N)
{
    int tot = 0;
    while (bfs())
    {
        for (int i = 0; i <= N; i++)
            cur[i] = fir[i];
        while (int temp = dfs(st, 2*inf))
            tot += temp;
    }
    return tot;
}
int main()
{
    while (scanf("%d%d", &n, &m) !=EOF)
    {
        memset(deg, 0, sizeof(deg));
        memset(fir, -1, sizeof(fir));
        cnt = 0;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d", &wom[i]);
            deg[i + n] -= wom[i];
            deg[n + m + 1] += wom[i];
        }
        int sum = 0, tot = 0;
        for (int i = 1; i <= n; i++)
        {
            int num;
            scanf("%d%d", &num, &day[i]);
            for (int j = 1; j <= num; j++)
            {
                int v, l, r;
                scanf("%d%d%d", &v, &l, &r);
                v++;
                L[++sum] = l;
                R[sum] = r;
                deg[i] -= L[sum];
                deg[n + v] += L[sum];
                addedge(i, v + n, R[sum] - L[sum]);
                addedge(v + n, i, 0);
            }
        }
        for (int i = 1; i <= n; i++)
        {
            addedge(0, i, day[i]);
            addedge(i, 0, 0);
        }
        for (int i = 1; i <= m; i++)
        {
            addedge(i + n, n + m + 1, inf-wom[i]);
            addedge(n + m + 1, i + n, 0);
        }
        
        for (int i = 0; i <= n + m + 1; i++)
        {
            if (deg[i] > 0)
            {
                tot += deg[i];
                addedge(n + m + 2, i, deg[i]);
                addedge(i, n + m + 2, 0);
            }
            else if (deg[i] < 0)
            {
                addedge(i, n + m + 3, -deg[i]);
                addedge(n + m + 3, i, 0);
            }
        }
        addedge(n + m + 1, 0, inf);
        addedge(0, n + m + 1, 0);
        st = n + m + 2;
        ed = n + m + 3;
        int flow = dinic(n+m+3);
        if (flow != tot)
            puts("-1");
        else
        {
            st = 0;
            ed = n + m + 1;
            flow = edge[cnt - 1].w;
            fir[st] = edge[fir[st]].nxt;
            fir[ed] = edge[fir[ed]].nxt;
            flow += dinic(n+m+1);
            printf("%d\n", flow);
            for (int i = 0; i < sum; i++)
                printf("%d\n", L[i+1]+edge[(i*2)^1].w);
        }
        puts("");
    }
    return 0;
}