题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5644

题意：

每天都有p[i]个飞行员进行阅兵，飞行员只工作一天。

m个休假公式，花费tt[i]元让飞行员在休假ss[i]天后回来上班。

可以花费Q元雇佣新的飞行员，但是直到P天后才能上班。

分析：

首先某一天雇佣的飞行员有三种可能：

1.原来就有的：

• 从s到第一天的结点连一条容量为k，费用为0的边。
• 从第i天向第i+1天连一条容量为INF，费用为0的边。

2.新雇佣的：

• 新雇佣的飞行员必须在P天后使用，所以在s和第P天的结点连一条容量为INF，费用为Q的边。

3.放假回来的：

（这里就不知道应该怎么处理了。）

其实仔细想，将每一天的结点都拆成两个，其中一个表示正常上班的情况，另一个用于表示飞行员休假回来上班的情况。也就是说：

• 在第x[i]和第y[i+tt]结点之间连一条容量为INF，费用为ss的边，表示第i+tt天用的是第i天开始休假tt天后回来的飞行员的情况。

最后从s到x[i]建一条容量为p[i]，费用为0的边，在y[i]到t同样建一条容量为p[i]，费用为0的边，然后跑一下最小费用流判断是否满流就好啦~！

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<queue>

using namespace std;

const int maxm = 505;

const int INF = 0x3f3f3f3f;

int s, t, tot, all = 0;

int dist[maxm], prevv[maxm], preve[maxm], head[maxm];

bool in[maxm];

int maxflow;

struct Edge{ int from, to, next, cap, cost;}edge[maxm<<2];

void add_edge(int from, int to, int cap, int cost)

{

   edge[tot].to = to;

   edge[tot].from = from;

   edge[tot].cap = cap;

   edge[tot].cost = cost;

   edge[tot].next = head[from];

   head[from] = tot++;

   edge[tot].to = from;

   edge[tot].from = to;

   edge[tot].cap = 0;

   edge[tot].cost = -cost;

   edge[tot].next = head[to];

   head[to] = tot++;

}

bool spfa(int s, int t)

{

    memset(dist, 0x3f, sizeof(dist));

    memset(in, false, sizeof(in));

    queue<int>q;

    q.push(s);

    in[s] = true;

    dist[s]=0;

    while(!q.empty()){

        int u = q.front();q.pop();

        in[u] = false;

        for(int i = head[u]; i != -1; i = edge[i].next){

            Edge e = edge[i];

            if(e.cap >0 && dist[e.to] > dist[u] + e.cost){

                dist[e.to] = dist[u] + e.cost;

                prevv[e.to] = u, preve[e.to] = i;

                if(!in[e.to]){

                    in[e.to] = true;

                    q.push(e.to);

                }

            }

        }

    }

    if(dist[t] == INF) return false;

    return true;

}

int MCMF(int s, int t)

{

    int flow = 0, cost = 0;

    while(spfa(s, t)){

        int d = INF;

        for(int i = t; i != s; i = prevv[i]){

            d = min(d, edge[preve[i]].cap);

        }

        flow += d;

        cost += dist[t] * d;

        for(int i = t; i != s; i = prevv[i]){

            edge[preve[i]].cap -= d;

            edge[preve[i]^1].cap += d;

        }

    }

    maxflow = flow;

    return cost;

}

int main (void)

{

    int T;scanf("%d",&T);

    while(T--){

        tot = 0;

        memset(head, -1, sizeof(head));

        int n, k; scanf("%d%d",&n, &k);

        int s = 0, t = 2 * n + 1;

        add_edge(s, n + 1, k, 0);

        int p, ss, tt;

        int all = 0;

        for(int i = 1; i <= n; i++){

             scanf("%d", &p);

             all += p;

             add_edge(s, i, p, 0);

             add_edge(i + n, t, p, 0);

        }

        for(int i = 1; i < n; i++)

            add_edge(i + n, i + n +1, INF, 0);

        int m, P, Q;

        scanf("%d%d%d",&m, &P, &Q);

        for(int i = P; i <= n; i++)

            add_edge(s, i + n, INF, Q);

        for(int i = 0; i < m; i++){

            scanf("%d%d",&ss, &tt);

            for(int j = 1; j <= n - tt; j++)

                add_edge(j, n + j + tt, INF, ss);

        }

        int res =MCMF(s, t);

        if(maxflow != all) printf("No solution\n");

        else printf("%d\n",res);

    }

}

其实建图还是挺难想的。。。。