Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 725 Solved: 380
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”。注意,由于程设老师良心大大的坏,所以他
是可以不把濒死的研究生送去医院的!。
Input本题包含多组数据;第一行是一个数T(T<=11),表示数据组数,以下T组数据。
对于每一组数据,第一行三个数,n,m,k;
以下一行n个数,表示a[1]…a[n]
接着一行2m个数,表示l[1],p[1]…l[n],p[n]
接着一行2k个数,表示d[1],q[1]…d[n],q[n]
n,m,k<=50,其余数均小于等于100.
Output对于每组数据以样例的格式输出一行,两个数分别表示第几组数据和最少钱数。
Sample Input2
3 2 1
10 20 30
40 90 15 100
1 5
3 2 1
10 20 30
40 90 15 100
2 5
Case 1: 4650
Case 2: impossible
样例解释:
买下90块钱的那40个研究生,另外再买10个100块钱的。这样,第一天用完的10个人全部送到医院,那么他们在第
三天可以继续使用;同时,第二天和第三天都用新的研究生来弥补,这样一共需要花费40*90 + 10*100 + 5*10 =
4650元。
/**************************************************************
Problem: 3280
User: ictsing
Language: C++
Result: Accepted
Time:664 ms
Memory:1588 kb
****************************************************************/
//BZOJ3280 小R的烦恼
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int inf = 1e9;
int s=0,t=3000+1;
const int mt = 3000+5;
int fr[12000+5],to[12000+5],nxt[12000+5],cap[12000+5],cost[12000+5],adj[mt],cur[mt];
bool inq[mt];
int dis[mt],lev[mt];
int ecnt=1;
int qwq[mt];
int ans1=0,ans2=0;
queue<int>q;
int n,m,k;
int sum=0;
int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
void adde(int u,int v,int cc,int ccc)
{
ecnt++,fr[ecnt]=u,to[ecnt]=v,nxt[ecnt]=adj[u],cap[ecnt]=cc,cost[ecnt]=ccc,adj[u]=ecnt;
ecnt++,fr[ecnt]=v,to[ecnt]=u,nxt[ecnt]=adj[v],cap[ecnt]=0,cost[ecnt]=-ccc,adj[v]=ecnt;
}
bool spfa()
{
while(!q.empty()) q.pop();
for(int i=s;i<=t;i++) dis[i]=inf,inq[i]=0;
q.push(s),dis[s]=0,inq[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();inq[u]=0;
for(int i=adj[u];i;i=nxt[i])
{
int v=to[i];
if(dis[v]>dis[u]+cost[i]&&cap[i])
{
dis[v]=dis[u]+cost[i];cur[v]=i;
if(!inq[v]) inq[v]=1,q.push(v);
}
}
}
return dis[t]!=inf;
}
void mcf()
{
while(spfa())
{
int tmp=inf;
for(int i=cur[t];i;i=cur[fr[i]]) tmp=min(tmp,cap[i]);
ans1+=tmp;
ans2+=dis[t]*tmp;
for(int i=cur[t];i;i=cur[fr[i]]) cap[i]-=tmp,cap[i^1]+=tmp;
}
}
void build()
{
ecnt=1;
memset(adj,0,sizeof(adj));
for(int i=1;i<=n;i++)
{
int x=read();
sum+=x;
adde(s,i,x,0);
adde(n+m+i,t,x,0);
if(i<n) adde(n+m+i,n+m+i+1,inf,0);
}
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
adde(s,i+n,x,y);
for(int j=n+m+1;j<=n*2+m;j++)
adde(i+n,j,inf,0);
}
for(int i=1;i<=k;i++)
{
int x=read(),y=read();
for(int j=1;j+x+1<=n;j++)
adde(j,j+x+n+m+1,inf,y);
}
}
int main()
{
int T_T=read();
for(int i=1;i<=T_T;i++)
{
n=read(),m=read(),k=read();
sum=0;
ans1=0,ans2=0;
build();
mcf();
printf("Case %d: ",i);
if(ans1<sum) puts("impossible");
else printf("%d\n",ans2);
}
return 0;
}
评论