HDU 5644 (费用流）

Problem King's Pilots （HDU 5644）

题目大意

　　举办一次持续n天的飞行表演，第i天需要P个飞行员。共有m种休假计划，每个飞行员表演1次后，需要休假S天，并提供T报酬来进行下一次表演。刚开始拥有k个飞行员。也可以招募飞行员来进行表演（数量无限），需要提供报酬q，在p天后参加表演。询问使表演顺利进行的最少花费，若无法进行，输出No solution。

解题分析

　　搬运官方题解：

　　

　　稍微解释一下：

　　首先忽略X。Y向T的流量表示第i天有多少人参加表演（第2条）。S向Y的流量表示有多少人可以参加第一天的表演(第3条），并且可以累积到后几天来参加表演（第6条）。S向Y的流量表示招募得到的飞行员（第4条）。

　　接下来考虑X。X是用来解决休假问题的。X向Y的流量表示到第i天已完成表演的的飞行员休假后从第j天开始可参加表演（第7条）。S向X的流量保证了休假的飞行员一定是已参加过表演的（第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();

     }

 }