BZOJ3280: 小R的烦恼
2024-08-22 17:32:02
题解:
随便建一下图费用流就可以过吧。。。
代码:
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 100000+5
#define maxm 100000+5
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int n,m,k,mincost,maxflow,tot=,s,ss,t,sum,a[maxn],head[maxn],d[maxn],from[*maxm];
bool v[maxn];
queue<int>q;
struct edge{int from,go,next,v,c;}e[*maxm];
void add(int x,int y,int z,int w)
{
e[++tot]=(edge){x,y,head[x],z,w};head[x]=tot;
e[++tot]=(edge){y,x,head[y],,-w};head[y]=tot;
}
bool spfa()
{
for (int i=s;i<=t;i++){v[i]=;d[i]=inf;}
q.push(s);d[s]=;v[s]=;
while(!q.empty())
{
int x=q.front();q.pop();v[x]=;
for (int i=head[x],y;i;i=e[i].next)
if(e[i].v&&d[x]+e[i].c<d[y=e[i].go])
{
d[y]=d[x]+e[i].c;from[y]=i;
if(!v[y]){v[y]=;q.push(y);}
}
}
return d[t]!=inf;
}
void mcf()
{
mincost=;maxflow=;
while(spfa())
{
int tmp=inf;
for(int i=from[t];i;i=from[e[i].from]) tmp=min(tmp,e[i].v);
mincost+=d[t]*tmp;maxflow+=tmp;
for(int i=from[t];i;i=from[e[i].from]){e[i].v-=tmp;e[i^].v+=tmp;}
}
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int T=read(),cs=;
while(T--)
{
n=read();m=read();k=read();sum=;
s=;ss=*n+;t=ss+;
memset(head,,sizeof(head));tot=;
for1(i,n)
{
a[i]=read();sum+=a[i];
add(s,i,a[i],);
add(i+n,t,a[i],);
}
for1(i,n-)add(i,i+,inf,);
for1(i,m)
{
int x=read(),y=read();
add(s,ss,x,y);
}
for1(i,n)add(ss,i+n,inf,);
for1(i,k)
{
int x=read(),y=read();
for1(j,n-x-)add(j,j+x++n,inf,y);
}
mcf();
printf("Case %d: ",++cs);
if(maxflow!=sum)printf("impossible\n");else printf("%d\n",mincost);
} return ;
}
3280: 小R的烦恼
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 138 Solved: 62
[Submit][Status]
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
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
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.
Source
最新文章
- RabbitMQ学习系列(二): RabbitMQ安装与配置
- scalatest的userguide
- 转:C# 中 MSCHART 饼状图显示百分比
- Oracle VM VirtualBox配置文件
- UED
- js命名空间笔记
- Checking For User Permissions Before Updating or Inserting The Records in Oracle Forms
- 根据日期字符串获取星期几,日期获取星期,时间获取星期,js获取星期
- (8/18)重学Standford_iOS7开发_协议、block、动画_课程笔记
- WPF 格式化输出- IValueConverter接口的使用
- Tomcat7.0更改默认的路径来访问自己的项目
- Xamarin移动跨平台解决方案是如何工作
- Hadoop集群搭建的密钥配置SSH实现机制
- Oracle集合操作
- deeplearning.ai 人工智能行业大师访谈 Geoffrey Hinton 听课笔记
- LinuxMint18使用单独分区作为Home挂载点
- d3实现家族树
- DecimalFormat 的用法
- web(六)css的基本语法、取值与单位
- confd
热门文章
- VS2005打开VS2008 VS2010 VS2012
- Spark Streaming揭秘 Day4-事务一致性(Exactly one)
- Django工程读取mongodb并使用分页器
- 对vector等STL标准容器的排序操作
- java 构造函数
- 【BZOJ 1412】[ZJOI2009]狼和羊的故事
- Linux桌面扩展 Docky
- Java发送邮件(带附件)
- 1003: [ZJOI2006]物流运输trans - BZOJ
- 团体程序设计天梯赛-练习集L1-016. 查验身份证