1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
|
#include<bits/stdc++.h> using namespace std;
const int maxn = 5050; const int INF = 1e9;
int t; int c[2010]; int p,m,f,n,s;
struct edge{ int from,to,cap,flow,cost; };
struct MCMF{ int n,m,s,t; vector<edge> edges; vector<int> G[maxn]; int d[maxn]; int inq[maxn]; int p[maxn]; int a[maxn];
void init(int n){ this->n = n; for(int i=0;i<=n;i++)G[i].clear(); edges.clear(); }
void addedge(int from,int to,int cap,int cost){ edges.push_back(edge{from,to,cap,0,cost}); edges.push_back(edge{to,from,0,0,-cost}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); }
bool spfa(int s,int t,int &flow,long long &cost){ for(int i=0;i<=n;i++)d[i] = INF; memset(inq,0,sizeof(inq)); d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; queue<int> q; q.push(s); while(!q.empty()){ int u = q.front(); q.pop(); inq[u] = 0; for(int i=0;i<G[u].size();i++){ edge &e = edges[G[u][i]]; if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){ d[e.to] = d[u] + e.cost; p[e.to] = G[u][i]; a[e.to] = min(a[u],e.cap-e.flow); if(!inq[e.to]){ q.push(e.to); inq[e.to] = 1; } } } } if(d[t]==INF)return false; flow+=a[t]; cost+=1LL*d[t]*a[t]; int u = t; while(u!=s){ edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; u = edges[p[u]].from; } return true; }
long long mincost(int s,int t){ int flow = 0; long long cost = 0; while(spfa(s,t,flow,cost)); return cost; } }solver;
int main(){ scanf("%d",&t); for(int i=1;i<=t;i++)scanf("%d",&c[i]); scanf("%d%d%d%d%d",&p,&m,&f,&n,&s); solver.init(2*t+1); for(int i=1;i<=t;i++){ solver.addedge(0,i,c[i],0); solver.addedge(i+t,2*t+1,c[i],0); solver.addedge(0,i+t,INF,p); if(i!=t)solver.addedge(i,i+1,INF,0); if(i+m<=t)solver.addedge(i,i+t+m,INF,f); if(i+n<=t)solver.addedge(i,i+t+n,INF,s); } long long res = solver.mincost(0,2*t+1); printf("%lldn",res); return 0; }
|
近期评论