题目链接
\(Solution\)
这道题很像餐巾计划啊。
- 首先将每天拆成\(x\)和\(x'\),\(S->x\)流量为\(a_i\)，费用为\(0\)表示一天下来有\(a_i\)个濒死的人, 再将\(x'->T\)流量为\(a_i\)表示一天需要有\(a_i\)个人
- 对于每个学校新建一个节点，将\(S\)和他相连流量为\(l_i\),在将这个节点和\(x'\)相连流量为\(inf\)，费用为\(p_i\)表示每天可以在学校中选人
- 然后在将\(x\)连向\(x+1\),流量为\(inf\),费用为\(0\)表示将濒死的人留到第二天。
- \(x\)连向\(x'+d_i+1\),流量为\(inf\),费用为\(q_i\)表示将濒死的人送进医院在第\(d_i+1\)的时候出院
\(Code\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=1e9+7;
int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9')
x=x*10+c-'0',c=getchar();
return x*f;
}
struct node{
int to,next,v,w;
}a[1000001];
int dis[10001],f[10001],pre[10001],fa[10001],s,t=10000,head[10001],cnt;
void add(int x,int y,int c,int v){
a[++cnt].to=y,a[cnt].next=head[x],a[cnt].v=c,a[cnt].w=v,head[x]=cnt;
a[++cnt].to=x,a[cnt].next=head[y],a[cnt].v=0,a[cnt].w=-v,head[y]=cnt;
}
queue<int>q;
int spfa(){
q.push(s);
memset(dis,127,sizeof(dis));
memset(f,0,sizeof(f));
f[s]=1,dis[s]=0;
int Inf=dis[s+1];
while(!q.empty()){
int now=q.front();
q.pop();
f[now]=0;
for(int i=head[now];i;i=a[i].next){
int v=a[i].to;
if(dis[v]>dis[now]+a[i].w&&a[i].v){
dis[v]=dis[now]+a[i].w,pre[v]=i,fa[v]=now;
if(!f[v])
f[v]=1,q.push(v);
}
}
}
if(dis[t]!=Inf)
return 1;
return 0;
}
int ans1,ans,x,y;
void anser(){
ans1=0,ans=0;
while(spfa()){
int minx=2147483647;
for(int i=t;i!=s;i=fa[i])
minx=min(minx,a[pre[i]].v);
ans+=minx,ans1+=dis[t]*minx;
for(int i=t;i!=s;i=fa[i])
a[pre[i]].v-=minx,(pre[i]%2)?a[pre[i]+1].v+=minx:a[pre[i]-1].v+=minx;
}
}
int main(){
int T=read();
for(int tt=1;tt<=T;tt++){
memset(head,0,sizeof(head)),cnt=0;
int n=read(),m=read(),k=read(),sum=0;
for(int i=1;i<=n;i++){
x=read(),add(s,i,x,0),add(i+n,t,x,0),sum+=x;
if(i<n)
add(i,i+1,inf,0);
}
for(int j=1;j<=m;j++){
x=read(),y=read();
add(s,j+n+n,x,0);
for(int i=1;i<=n;i++)
add(j+n+n,i+n,inf,y);
}
for(int j=1;j<=k;j++){
x=read()+1,y=read();
for(int i=1;i<n;i++)
if(i+x<=n)
add(i,i+x+n,inf,y);
}
anser();
if(ans!=sum)
printf("Case %d: impossible\n",tt);
else
printf("Case %d: %d\n",tt,ans1);
}
}