【bzoj3280】小R的烦恼

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]

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
HINT

样例解释：买下90块钱的那40个研究生，另外再买10个100块钱的。这样，第一天用完的10个人全部送到医院，那么他们在第三天可以继续使用；同时，第二天和第三天都用新的研究生来弥补，这样一共需要花费40*90 + 10*100 + 5*10 = 4650元。
数据规模：
对于30%的数据中的每组数据,
满足n<=5,m,k<=2,其余数均小于等于100或者
n<=10,m,k<=10,其余数均小于等于20.
对于100%的数据
n,m,k<=50,其余数均小于等于100.

题解
与bzoj1221类似。
将每天拆成两个集合，xi表示健康的人，yi表示生病的人
源点->yi 容量为a[i]，费用为0 因为一天最多产生a[i]个病人
xi->汇点 容量为a[i]，费用为0
yi->xi+d[x] 容量为inf ,费用为q[i]
源点->每个大学 容量为l[i] ，费用为0
每个大学->x集合中的每个点 容量为inf ，费用为p[i]
xi->xi+1 容量为inf ,费用为0

代码

#include
#define ll long long
#define inf 0x7fffffff
#define mod 1000000007
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int n,m,k,ans2,ans1,sum,tot,S,T;
int from[2005],q[2005],dis[2005],Head[2005];
bool vis[2005];
struct data{int from,to,next,w,c;}e[1000001];
inline void ins(int u,int v,int w,int c)
{tot++;e[tot].to=v;e[tot].from=u;e[tot].w=w;e[tot].c=c;e[tot].next=Head[u];Head[u]=tot;
}
inline void insert(int u,int v,int w,int c)
{ins(u,v,w,c);ins(v,u,0,-c);
}
inline bool spfa()
{for (int i=0;i<=T;i++) dis[i]=inf;queue<int>q;q.push(S);dis[S]=0;vis[S]=1;while (!q.empty()){int now=q.front();q.pop();for (int i=Head[now];i;i=e[i].next)if (dis[e[i].to]>dis[now]+e[i].c&&e[i].w){from[e[i].to]=i;dis[e[i].to]=dis[now]+e[i].c;if (!vis[e[i].to]){vis[e[i].to]=1;q.push(e[i].to);}}vis[now]=0;}if (dis[T]==inf)return 0;return 1;
}
void mcf()
{int i=from[T],x=inf;while (i){x=min(x,e[i].w);i=from[e[i].from];}i=from[T];ans1+=x;while (i){ans2+=e[i].c*x;e[i].w-=x;e[i^1].w+=x;i=from[e[i].from];}
}
int main()
{int Case=read(),cnt=0;while (Case--){cnt++;printf("Case %d: ",cnt);n=read();m=read();k=read();S=n+m+n+1;T=S+1;tot=1;sum=0;memset(Head,0,sizeof(Head));for (int i=1;i<=n;i++){int x=read();sum+=x;insert(i+n+m,T,x,0);insert(S,i+m,x,0);if (i+1<=n) insert(i+m,i+m+1,inf,0);}for (int i=1;i<=m;i++){int l=read(),p=read();insert(S,i,l,0);for (int j=1;j<=n;j++)insert(i,j+m+n,inf,p);}for (int i=1;i<=k;i++){int d=read(),q=read();for (int j=1;j<=n;j++)if (j+d+1<=n) insert(j+m,j+m+n+d+1,inf,q);}ans1=ans2=0;while (spfa()) mcf();if (ans1!=sum) puts("impossible");else printf("%d\n",ans2);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！