【BestCoder Round #75 1005】King's Pilots

  费用流建模和BZOJ1221，网络流24题里的餐巾计划是差不多的。

  但是由于刚开始有k的飞行员，所以要从S向Y1连一条容量为k费用为0的边，并且每个Yi到Yi+1连一条容量为无穷大费用为0的边，以使用这k个飞行员。

#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;
}