洛谷P1251 餐巾计划问题

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long LL;
  4 const int MAXN=5000;
  5 const int MAXM=30000;
  6 const LL INF=1e18;
  7 struct Edge{
  8     int to,Next;
  9     LL cap,flow,cost;
 10 }edge[MAXM];
 11 int head[MAXN],tol;
 12 int pre[MAXN];
 13 LL dis[MAXN];
 14 bool vis[MAXN];
 15 int N;
 16 void init(int n){
 17     N=n;
 18     tol=0;
 19     memset(head,-1,sizeof(head));
 20 }
 21 void addedge(int u,int v,LL cap,LL cost){
 22     edge[tol].to=v;
 23     edge[tol].cap=cap;
 24     edge[tol].cost=cost;
 25     edge[tol].flow=0;
 26     edge[tol].Next=head[u];
 27     head[u]=tol++;
 28     edge[tol].to=u;
 29     edge[tol].cap=0;
 30     edge[tol].cost=-cost;
 31     edge[tol].flow=0;
 32     edge[tol].Next=head[v];
 33     head[v]=tol++;
 34 }
 35 bool spfa(int s,int t){
 36     queue<int> q;
 37     for(int i=0;i<N;i++){
 38         dis[i]=INF;
 39         vis[i]=false;
 40         pre[i]=-1;
 41     }
 42     dis[s]=0;
 43     vis[s]=true;
 44     q.push(s);
 45     while(!q.empty()){
 46         int u=q.front();
 47         q.pop();
 48         vis[u]=false;
 49         for(int i=head[u];i!=-1;i=edge[i].Next){
 50             int v=edge[i].to;
 51             if(edge[i].cap>edge[i].flow &&
 52                dis[v]>dis[u]+edge[i].cost){
 53                 dis[v]=dis[u]+edge[i].cost;
 54                 pre[v]=i;
 55                 if(!vis[v]){
 56                     vis[v]=true;
 57                     q.push(v);
 58                 }
 59             }
 60         }
 61     }
 62     if(pre[t]==-1)  return false;
 63     else    return true;
 64 }
 65 LL minCostMaxflow(int s,int t,LL &cost){
 66     LL flow=0;
 67     cost=0;
 68     while(spfa(s,t)){
 69         LL Min=INF;
 70         for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
 71             if(Min>edge[i].cap-edge[i].flow)
 72                 Min=edge[i].cap-edge[i].flow;
 73         }
 74         for(int i=pre[t];i!=-1;i=pre[edge[i^1].to]){
 75             edge[i].flow+=Min;
 76             edge[i^1].flow-=Min;
 77             cost+=edge[i].cost*Min;
 78         }
 79         flow+=Min;
 80     }
 81     return flow;
 82 }
 83 
 84 LL r[2000+5];
 85 int main(){
 86     int tN;
 87     scanf("%d",&tN);
 88     for(int i=1;i<=tN;i++)
 89         scanf("%lld",&r[i]);
 90     int m1,n1;
 91     LL p1,f1,s1;
 92     scanf("%lld%d%lld%d%lld",&p1,&m1,&f1,&n1,&s1);
 93     init(tN*2+2);
 94     int s=0,t=tN*2+1;
 95     
 96     for(int i=1;i<tN;i++){
 97         addedge(i+tN,i+1+tN,INF,0);
 98     }
 99     for(int i=1;i<=tN;i++){
100         addedge(s,i,INF,p1);
101         addedge(i,t,r[i],0);
102         addedge(s,i+tN,r[i],0);
103         if(i+m1<=tN)
104             addedge(i+tN,i+m1,INF,f1);
105         if(i+n1<=tN)
106             addedge(i+tN,i+n1,INF,s1);
107     }
108     LL ans;
109     minCostMaxflow(s,t,ans);
110     printf("%lld\n",ans);
111     return 0;
112 }