BZOJ3280: 小R的烦恼

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 Input

2
3 2 1
10 20 30
40 90 15 100
1 5
3 2 1
10 20 30
40 90 15 100
2 5

Sample Output

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;

}

 

评论

热度(4)