【BestCoder Round #75 1005】King's Pilots
费用流建模和BZOJ1221，网络流24题里的餐巾计划是差不多的。
但是由于刚开始有k的飞行员，所以要从S向Y1连一条容量为k费用为0的边，并且每个Yi到Yi+1连一条容量为无穷大费用为0的边，以使用这k个飞行员。
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 101 102 103 | #include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn=210,maxv=410,inf=~0U>>1;int head[maxv<<1],net[maxv<<4],E[maxv<<4],F[maxv<<4],C[maxv<<4],Ecnt;int P[maxn];int s[maxn],t[maxn];int n,k,m,p,q;int S,T;void Add_Edge(int x,int y,int flow,int cost){ net[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;F[Ecnt]=0;C[Ecnt]=cost; net[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;F[Ecnt]=flow;C[Ecnt]=-cost;}int vis[maxv];int Q[maxv],qhead,qtail;int dis[maxv];int prev[maxv];int inc(int x) {return x==maxv-1?0:x+1;}int dec(int x) {return x==0?maxv-1:x-1;}bool Spfa(int st,int ed){ memset(vis,0,sizeof(vis)); memset(dis,0x7F,sizeof(dis)); Q[qhead=qtail=0]=st; vis[st]=1;dis[st]=0; while (qhead!=inc(qtail)) { int x=Q[qhead]; qhead=inc(qhead); vis[x]=0; for (int i=head[x];i;i=net[i]) if (F[i] && dis[E[i]]>dis[x]-C[i]) { dis[E[i]]=dis[x]-C[i]; if (!vis[E[i]]) if (qhead!=inc(qtail) && dis[Q[qhead]]>dis[E[i]]) Q[qhead=dec(qhead)]=E[i];else Q[qtail=inc(qtail)]=E[i]; vis[E[i]]=1; } } return dis[ed]!=0x7F7F7F7F;}int DFS(int x,int flow,int &res){ vis[x]=1; if (x==T) return flow; int rest=flow; for (int i=head[x];i && rest;i=net[i]) if (dis[E[i]]==dis[x]-C[i] && F[i^1] && !vis[E[i]]) { int d=DFS(E[i],min(rest,F[i^1]),res); res+=d*C[i]; rest-=d;F[i]+=d;F[i^1]-=d; } return flow-rest;}void Min_Cost_Flow(){ int res=0; while (Spfa(T,S)) { vis[T]=1; while (vis[T]) { memset(vis,0,sizeof(vis)); DFS(S,inf,res); } } printf("%d\n",res);}int main(){ int TT; scanf("%d",&TT); while (TT--) { memset(head,0,sizeof(head)); Ecnt=1; scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) scanf("%d",&P[i]); scanf("%d%d%d",&m,&p,&q); int psum=0;for (int i=1;i<p;i++) psum+=P[i];if (psum>k) {puts("No solution");continue;} for (int i=1;i<=m;i++) scanf("%d%d",&s[i],&t[i]); S=2*n+1;T=S+1; Add_Edge(S,n+1,k,0); for (int i=1;i<=n;i++) Add_Edge(S,i,P[i],0); for (int i=1;i<=n;i++) Add_Edge(i+n,T,P[i],0); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (t[j]+i<=n) Add_Edge(i,i+n+t[j],inf,s[j]); for (int i=1;i<n;i++) Add_Edge(i,i+1,inf,0),Add_Edge(i+n,i+n+1,inf,0); for (int i=p;i<=n;i++) Add_Edge(S,i+n,inf,q); Min_Cost_Flow(); } return 0;} |
评论 (0)
