餐巾

【问题描述】

一个餐厅在相继的N天里，第i天需要Ri块餐巾(i=l，2，…，N)。餐厅可以从三种途径获得餐巾。

(1)购买新的餐巾，每块需p分；

(2)把用过的餐巾送到快洗部，洗一块需m天，费用需f分(f<p)。如m=l时，第一天送到快洗部的餐巾第二天就可以使用了，送慢洗的情况也如此。

(3)把餐巾送到慢洗部，洗一块需n天(n>m)，费用需s分(s<f)。

在每天结束时，餐厅必须决定多少块用过的餐巾送到快洗部，多少块送慢洗部。在每天开始时，餐厅必须决定是否购买新餐巾及多少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使N天总的费用最小。

【输入】

输入文件共 3 行，第 1 行为总天数；第 2 行为每天所需的餐巾块数；第 3 行为每块餐巾的新购费用 p ，快洗所需天数 m ，快洗所需费用 f ，慢洗所需天数 n ，慢洗所需费用 s 。

【输出】

一行，最小的费用

【样例】

napkin.in

3
3 2 4
10 1 6 2 3

napkin.out

【数据规模】

n<=200,Ri<=50

solution

考虑每一天的餐巾来源：买新的餐巾 OR 用快/慢洗完的餐巾

每一天当做一个节点

对于买新的餐巾：

S 向第i天连容量为R[i] 费用为0 的边，第i天向T连容量为INF 费用为p的边

对于用洗完的餐巾：

新建一层节点表示第i天用完的餐巾记作i'

快洗：第i天向第(i-m)'天连INF f 的边

慢洗：同上

由于第i天洗完的，在第i天以后也可以用，把每个相邻的天连起来

(ps：做这题的时候，因为没有分清i*2和i+n的区别，卡了2小时......)

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<iostream>
  5 #define mem(a,b) memset(a,b,sizeof(a))
  6 #define ll long long
  7 #define dd double
  8 using namespace std;
  9 const int INF=(1<<31)-1;
 10 inline int minn(int a,int b){return a<b?a:b;}
 11 struct son
 12 {
 13     int u,v,next;
 14     int w,cost;
 15 };
 16 son a1[3000006];
 17 int first[3000006],e;
 18 void addbian(int u,int v,int w,int cost)
 19 {
 20     a1[e].cost=cost;
 21     a1[e].v=v;
 22     a1[e].w=w;
 23     a1[e].u=u;
 24     a1[e].next=first[u];
 25     first[u]=e++;
 26 }
 27 void Link(int u,int v,int w,int cost)
 28 {
 29     addbian(u,v,w,cost);
 30     addbian(v,u,0,-cost);
 31 }
 32 
 33 int n,newmoney,manmoney,kuaimoney,mantian,kuaitian;
 34 int A[2006];
 35 int S,T;
 36 
 37 int d[2006],flag[2006],pre[2006],flow[2006];
 38 queue<int> q;
 39 bool spfa(int &fw,int &ct)
 40 {
 41     mem(d,0x7f/3);mem(flag,0);mem(pre,0);mem(flow,0x7f);
 42     int qqq=d[0];
 43     q.push(S);d[S]=0;flag[S]=1;
 44     while(!q.empty())
 45     {
 46         int now=q.front();q.pop();flag[now]=0;
 47         for(int i=first[now];i!=-1;i=a1[i].next)
 48         {
 49             int temp=a1[i].v;
 50             if(!a1[i].w||d[temp]<=d[now]+a1[i].cost)continue;
 51             d[temp]=d[now]+a1[i].cost;
 52             pre[temp]=i;
 53             flow[temp]=minn(flow[now],a1[i].w);
 54             if(!flag[temp]){q.push(temp);flag[temp]=1;}
 55         }
 56     }
 57     if(d[T]==qqq)return 0;
 58     fw+=flow[T];ct+=d[T]*flow[T];
 59     int now=T;
 60     while(now!=S)
 61     {
 62         a1[pre[now]].w-=flow[T];
 63         a1[pre[now]^1].w+=flow[T];
 64         now=a1[pre[now]].u;
 65     }
 66     return 1;
 67 }
 68 
 69 int MCMF()
 70 {
 71     int flow=0,cost=0;
 72     while(spfa(flow,cost));
 73     return cost;
 74 }
 75 
 76 void out11()
 77 {
 78     printf("
");
 79     for(int i=1;i<=n;++i)
 80     {
 81         printf("i=%d
",i);
 82         for(int j=first[i];j!=-1;j=a1[j].next)
 83           printf("%d ",a1[j].v);
 84         printf("
");
 85     }
 86     printf("
");
 87 }
 88 
 89 int main(){
 90     //freopen("1.txt","r",stdin);
 91     freopen("napkin.in","r",stdin);
 92     freopen("napkin.out","w",stdout);
 93     mem(first,-1);
 94     scanf("%d",&n);
 95     for(int i=1;i<=n;++i)scanf("%d",&A[i]);
 96     scanf("%d%d%d%d%d",&newmoney,&kuaitian,&kuaimoney,&mantian,&manmoney);
 97     S=0;T=n*2+1;
 98     
 99     for(int i=1;i<=n;++i){Link(S,i,A[i],0);Link(i,T,INF,newmoney);}
100     for(int i=1;i<=n;++i)
101     {
102         if(i+kuaitian<=n)Link(i+kuaitian,i+n,INF,kuaimoney);
103         if(i+mantian<=n)Link(i+mantian,i+n,INF,manmoney);
104     }
105     for(int i=1;i<n;++i)Link(i+1,i,INF,0);
106     for(int i=1;i<=n;++i)Link(i+n,T,A[i],0);
107     
108     //out11();
109     
110     printf("%d",MCMF());
111     //while(1);
112     return 0;
113 }

code