题目:

Description

小R最近遇上了大麻烦，他的程序设计挂科了。于是他只好找程设老师求情。善良的程设老师答应不挂他，但是要求小R帮助他一起解决一个难题。

问题是这样的，程设老师最近要进行一项邪恶的实验来证明P=NP，这个实验一共持续n天，第i天需要a[i]个研究生来给他搬砖。研究生毕竟也是人，所以雇佣研究生是需要钱的，机智的程设老师已经联系好了m所大学，第j所大学共有l[j]个研究生，同时雇佣这所大学的一个研究生需要p[j]元钱。

本来程设老师满心欢喜的以为，这样捡最便宜的max{a[i]}个研究生雇来，就可以完成实验；结果没想到，由于他要求硕士生们每天工作25个小时不许吃饭睡觉上厕所喝水说话咳嗽打喷嚏呼吸空气，因此一天下来给他搬砖的所有研究生都会进入濒死状态。濒死状态的研究生，毫无疑问，就不能再进行工作了。但是机智的老师早早联系好了k家医院，第i家医院医治一个濒死的研究生需要d[i]天,并且需要q[i]元钱。

现在，程设老师想要知道，最少花多少钱，能够在这n天中满足每天的需要呢？若无法满足，则请输出”impossible”。注意，由于程设老师良心大大的坏，所以他是可以不把濒死的研究生送去医院的！

题解:

但愿我将来能不会遇到这种程设老师

这道题不就是餐巾(网络流24题)吗...

建模如下:

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

inline void read(int &x){

	x=0;char ch;bool flag = false;

	while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;

	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;

}

const int maxn = 40010;

const int maxnode = 40010;

const int inf = 0x3f3f3f3f;

struct Edge{

	int to,next,cap,cost;

}G[maxnode<<1];

int head[maxnode],cnt=1;

void add(int u,int v,int c,int d){

	G[++cnt].to = v;

	G[cnt].next = head[u];

	head[u] = cnt;

	G[cnt].cap = c;

	G[cnt].cost = d;

}

inline void insert(int u,int v,int c,int d){

	add(u,v,c,d);add(v,u,0,-d);

}

#define v G[i].to

const int lim = maxnode<<1;

int dis[maxnode],flow[maxnode],p[maxnode],q[lim+10];

int S,T,l,r,ans,tot_flow;bool inq[maxnode];

inline bool spfa(){

	memset(dis,0x3f,sizeof dis);

	inq[S] = true;dis[S] = 0;

	flow[S] = inf;l = 0;r = -1;

	q[++r] = S;

	while(l <= r){

		int u = q[l % lim];++l;

		for(int i = head[u];i;i=G[i].next){

			if(dis[v] > dis[u] + G[i].cost && G[i].cap){

				dis[v] = dis[u] + G[i].cost;

				flow[v] =  min(flow[u],G[i].cap);

				p[v] = i;

				if(!inq[v]){

					q[++r % lim] = v;

					inq[v] = true;

				}

			}

		}inq[u] = false;

	}if(dis[T] == dis[T+1]) return false;

	ans += dis[T]*flow[T];

	tot_flow += flow[T];

	for(int u = T;u != S;u = G[p[u]^1].to)

		G[p[u]].cap -= flow[T],G[p[u]^1].cap += flow[T];

	return true;

}

#undef v

int a[maxn],L[maxn],P[maxn],D[maxn],Q[maxn];

inline void init(){

	memset(head,0,sizeof head);

	cnt = 1;tot_flow = 0;ans = 0;

}

inline void work(){

	init();

	int n,m,k;read(n);read(m);read(k);

	S = maxnode - 5;T = S + 1;

	for(int i=1;i<=n;++i){

		read(a[i]);tot_flow -= a[i];

		insert(i,T,a[i],0);

		insert(S,i+n,a[i],0);

		if(i != n) insert(i,i+1,inf,0);

	}

	for(int i=1;i<=m;++i){

		read(L[i]);read(P[i]);

		insert(S,1,L[i],P[i]);

	}

	for(int i=1;i<=k;++i){

		read(D[i]);read(Q[i]);

		for(int j=1;j<=n;++j){

			if(j + D[i] + 1 > n) break;

			insert(j+n,j+D[i]+1,inf,Q[i]);

		}

	}

	while(spfa());

	if(tot_flow < 0) puts("impossible");

	else printf("%d\n",ans);

}

int main(){

	int T;read(T);

	for(int i=1;i<=T;++i){

		printf("Case %d: ",i);

		work();

	}

	getchar();getchar();

	return 0;

}