Problem King's Pilots （HDU 5644）
题目大意
举办一次持续n天的飞行表演，第i天需要Pi个飞行员。共有m种休假计划，每个飞行员表演1次后，需要休假Si天，并提供Ti报酬来进行下一次表演。刚开始拥有k个飞行员。也可以招募飞行员来进行表演（数量无限），需要提供报酬q，在p天后参加表演。询问使表演顺利进行的最少花费，若无法进行，输出No solution。
解题分析
搬运官方题解：
稍微解释一下：
首先忽略Xi。Yi向T的流量表示第i天有多少人参加表演（第2条）。S向Y1的流量表示有多少人可以参加第一天的表演(第3条），并且可以累积到后几天来参加表演（第6条）。S向Yi的流量表示招募得到的飞行员（第4条）。
接下来考虑Xi。Xi是用来解决休假问题的。Xi向Yj的流量表示到第i天已完成表演的的飞行员休假后从第j天开始可参加表演（第7条）。S向Xi的流量保证了休假的飞行员一定是已参加过表演的（第1条），并且开始休假的时间可以是任意的（第5条）。
好厉害！好强！
参考程序
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std; #define V 1008
#define E 1000008
#define INF 200000000
int n,m,k,S,T,p,q,Que,num;
int ss[V],tt[V],P[V]; int pd[V],dis[V],pre[V];
struct line{
int u,v,c,w,nt;
}eg[E];
int lt[V],sum; void adt(int u,int v,int c,int w) {
eg[++sum].u=u; eg[sum].v=v; eg[sum].c=c;
eg[sum].w=w; eg[sum].nt=lt[u]; lt[u]=sum;
} void add(int u,int v,int c,int w) {
adt(u,v,c,w); adt(v,u,,-w);
// printf("%d %d %d %d\n",u,v,c,w);
} void init(){ sum=; num=;
memset(lt,,sizeof(lt));
scanf("%d%d",&n,&k);
for (int i=;i<=n;i++) { scanf("%d",&P[i]); num+=P[i]; }
scanf("%d%d%d",&m,&p,&q);
for (int i=;i<=m;i++) scanf("%d%d",&ss[i],&tt[i]); S=; T=n*+;
for (int i=;i<=n;i++) add(S,i,P[i],);
for (int i=;i<=n;i++) add(i+n,T,P[i],);
add(S,n+,k,);
for (int i=;i<=n;i++)
if (i>=p) add(S,i+n,INF,q);
for (int i=;i<n;i++) add(i,i+,INF,);
for (int i=n+;i<n*;i++) add(i,i+,INF,);
for (int j=;j<=m;j++)
for (int i=;i<=n;i++)
if (i+tt[j]<=n)
add(i,i+tt[j]+n,INF,ss[j]);
n=T; } bool spfa() {
queue <int> Q;
for (int i=;i<=n;i++) {
dis[i]=INF;
pd[i]=;
pre[i]=-;
}
dis[S]=; pd[S]=; Q.push(S);
while (!Q.empty()) {
int u = Q.front();
for (int i=lt[u];i;i=eg[i].nt)
if (eg[i].c>) {
int v=eg[i].v;
if (dis[u]+eg[i].w<dis[v]) {
dis[v]=dis[u]+eg[i].w;
pre[v]=i;
if (!pd[v]) {
Q.push(v);
pd[v]=;
}
}
}
pd[u]=;
Q.pop();
}
return dis[T]!=INF;
} void minCmaxF(){
int minC=,maxF=,flow;
while (spfa()) {
flow=INF;
for (int i=pre[T];~i;i=pre[eg[i].u])
flow=min(flow,eg[i].c);
for (int i=pre[T];~i;i=pre[eg[i].u]) {
eg[i].c-=flow;
eg[i^].c+=flow;
}
maxF+=flow;
minC+=flow*dis[T];
}
if (maxF==num) printf("%d\n",minC); else printf("No solution\n"); } int main(){
scanf("%d",&Que);
while (Que--) {
init();
minCmaxF();
}
}