2424. [HAOI2010]订货【费用流】

Description

某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单位产品要付存贮费用m，假定第一月月初的库存量为零，第n月月底的库存量也为零，问如何安排这n个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为S。

Input

第1行：n, m, S (0<=n<=50, 0<=m<=10, 0<=S<=10000)

第2行：U1 , U2 , ... , Ui , ... , Un (0<=Ui<=10000)

第3行：d1 , d2 , ..., di , ... , dn (0<=di<=100)

Output

只有1行，一个整数，代表最低成本

Sample Input

3 1 1000
2 4 8
1 2 4

Sample Output

一道比餐巾计划垃圾到不知道到哪里去的题
(好吧感觉和餐巾计划是一个题)
S---每一天，INF，当日单价
每一天---T，当日需求，0
每一天---下一天，S，m
啊做水题真爽

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<queue>

 #define id(x,y) (x-1)*m+y

 #define N (10000+10)

 #define M (1000000+10)

 using namespace std;

 bool used[N];

 int n,m,S,s,e,u[],d[];

 int num_edge,head[N];

 int dis[N],INF,pre[N];

 queue<int>q;

 struct node

 {

     int to,next,Flow,Cost;

 } edge[M*];

 void add(int u,int v,int l,int c)

 {

     edge[++num_edge].to=v;

     edge[num_edge].next=head[u];

     edge[num_edge].Flow=l;

     edge[num_edge].Cost=c;

     head[u]=num_edge;

 }

 bool Spfa(int s,int e)

 {

     memset(dis,0x7f,sizeof(dis));

     memset(pre,-,sizeof(pre));

     dis[s]=;

     used[s]=true;

     q.push(s);

     while (!q.empty())

     {

         int x=q.front();

         q.pop();

         for (int i=head[x]; i!=; i=edge[i].next)

             if (dis[x]+edge[i].Cost<dis[edge[i].to] && edge[i].Flow>)

             {

                 dis[edge[i].to]=dis[x]+edge[i].Cost;

                 pre[edge[i].to]=i;

                 if (!used[edge[i].to])

                 {

                     used[edge[i].to]=true;

                     q.push(edge[i].to);

                 }

             }

         used[x]=false;

     }

     return dis[e]!=INF;

 }

 int MCMF(int s,int e)

 {

     int Fee=;

     while (Spfa(s,e))

     {

         int d=INF;

         for (int i=e; i!=s; i=edge[((pre[i]-)^)+].to)

             d=min(d,edge[pre[i]].Flow);

         for (int i=e; i!=s; i=edge[((pre[i]-)^)+].to)

         {

             edge[pre[i]].Flow-=d;

             edge[((pre[i]-)^)+].Flow+=d;

         }

         Fee+=d*dis[e];

     }

     return Fee;

 }

 int main()

 {

     memset(&INF,0x7f,sizeof(INF));

     s=,e=;

     scanf("%d%d%d",&n,&m,&S);

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

         scanf("%d",&u[i]);

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

         scanf("%d",&d[i]);

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

     {

         add(s,i,INF,d[i]);

         add(i,s,,-d[i]);

         add(i,e,u[i],);

         add(e,i,,);

         if (i==n) break;

         add(i,i+,S,m);

         add(i+,i,,-m);

     }

     printf("%d",MCMF(s,e));

 }

巴特西