• 【bzoj1520】[POI2006]Szk-Schools

    【bzoj1520】[POI2006]Szk-Schools

    DescriptionInputOutput如果有可行解,输出最小代价,否则输出NIE.SampleInput5112311513255415103331SampleOutput9题解这个裸的费用流吧。。正好复习下zkw[crayon-5a12821e99ded574860223/]  ...

    12014年10月20日1,716费用流
  • 【bzoj2324】[ZJOI2011]营救皮卡丘

    【bzoj2324】[ZJOI2011]营救皮卡丘

    Description皮卡丘被火箭队用邪恶的计谋抢走了!这三个坏家伙还给小智留下了赤果果的挑衅!为了皮卡丘,也为了正义,小智和他的朋友们义不容辞的踏上了营救皮卡丘的道路。火箭队一共有N个据点,据点之间存在M条双向道路。据点分别从1到N标号。小智一行K人从真新镇出发,营救被困在N号据点的皮卡丘。为了方便起见,我们将真新镇视为0号据点,一开始K个人都在0号点。由于火箭队的重重布防,要想摧毁K号据点,必须按照顺序先摧...

    02014年10月9日3,178费用流,floyd
  • 【bzoj1930】[Shoi2003]pacman吃豆豆

    【bzoj1930】[Shoi2003]pacman吃豆豆

    Description两个PACMAN吃豆豆。一开始的时候,PACMAN都在坐标原点的左下方,豆豆都在右上方。PACMAN走到豆豆处就会吃掉它。PACMAN行走的路线很奇怪,只能向右走或者向上走,他们行走的路线不可以相交。请你帮这两个PACMAN计算一下,他们俩加起来最多能吃掉多少豆豆。Input第一行为一个整数N,表示豆豆的数目。接下来N行,每行一对正整数,表示第i个豆豆的坐标。任意两个豆豆的坐标都不会重合。O...

    92014年6月14日2,997费用流
  • 【bzoj2661】[BeiJing wc2012]连连看

    【bzoj2661】[BeiJing wc2012]连连看

    Description 凡是考智商的题里面总会有这么一种消除游戏。不过现在面对的这关连连看可不是QQ游戏里那种考眼力的游戏。我们的规则是,给出一个闭区间[a,b]中的全部整数,如果其中某两个数x,y(设x>y)的平方差x2-y2是一个完全平方数z2,并且y与z互质,那么就可以将x和y连起来并且将它们一起消除,同时得到x+y点分数。那么过关的要求就是,消除的数对尽可能多的前提下,得到足够的分数。快动手动笔算一算吧。Input 只有一行...

    82014年6月5日1,916费用流
  • 【NOIP模拟赛】密码锁

    【NOIP模拟赛】密码锁

    题目描述hzwer有一把密码锁,由N个开关组成。一开始的时候,所有开关都是关上的。当且仅当开关x1,x2,x3,...xk为开,其他开关为关时,密码锁才会打开。他可以进行M种的操作,每种操作有一个size[i],表示,假如他选择了第i种的操作的话,他可以任意选择连续的size[i]个格子,把它们全部取反。(注意,由于黄金大神非常的神,所以操作次数可以无限>_<)本来这是一个无关紧要的问题,但是,黄金大神不小心他的钱丢进去了,没有...

  • NOI2008志愿者招募

    NOI2008志愿者招募

    Description申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。经过估算,这个项目需要N天才能完成,其中第i天至少需要Ai个人。布布通过了解得知,一共有M类志愿者可以招募。其中第i类可以从第Si天工作到第Ti天,招募费用是每人Ci元。新官上任三把火,为了出色地完成自己的工作,布布希望用尽量少的费用招募足够的志愿者,...

    22014年5月31日2,453费用流
  • 【bzoj3280】小R的烦恼

    【bzoj3280】小R的烦恼

    Description小R最近遇上了大麻烦,他的程序设计挂科了。于是他只好找程设老师求情。善良的程设老师答应不挂他,但是要求小R帮助他一起解决一个难题。问题是这样的,程设老师最近要进行一项邪恶的实验来证明P=NP,这个实验一共持续n天,第i天需要a[i]个研究生来给他搬砖。研究生毕竟也是人,所以雇佣研究生是需要钱的,机智的程设老师已经联系好了m所大学,第j所大学共有l[j]个研究生,同时雇佣这所大学的一个研究生需要p[j]元...

    02014年5月8日1,522费用流
  • 【bzoj2879】[Noi2012]美食节

    【bzoj2879】[Noi2012]美食节

    DescriptionCZ市为了欢迎全国各地的同学,特地举办了一场盛大的美食节。作为一个喜欢尝鲜的美食客,小M自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而,尝鲜的欲望是难以满足的。尽管所有的菜品都很可口,厨师做菜的速度也很快,小M仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小M开始研究起了做菜顺序的问题,即安排一个做菜的顺序使得同学们的等待时间最短。小M发现,美食节...

    42014年5月1日3,608费用流
  • 【bzoj1070】[SCOI2007]修车

    【bzoj1070】[SCOI2007]修车

    Description同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。说明:顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。Input第一行有两个m,n,表示技术人员数与顾客数。接下来n行,每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的...

    122014年5月1日5,077费用流
  • 网络流&费用流模板

    网络流&费用流模板

    网络流dinic[crayon-5a12821ebe797390251180/]最小费用最大流spfa[crayon-5a12821ebe7ab801929274/]zkw费用流[crayon-5a12821ebe7b7573626246/] 

    132014年5月1日6,432最小割,费用流,最大流
  • 【bzoj2245】[SDOI2011]工作安排

    【bzoj2245】[SDOI2011]工作安排

    Description你的公司接到了一批订单。订单要求你的公司提供n类产品,产品被编号为1~n,其中第i类产品共需要Ci件。公司共有m名员工,员工被编号为1~m员工能够制造的产品种类有所区别。一件产品必须完整地由一名员工制造,不可以由某名员工制造一部分配件后,再转交给另外一名员工继续进行制造。我们用一个由0和1组成的m*n的矩阵A来描述每名员工能够制造哪些产品。矩阵的行和列分别被编号为1~m和1~n,Ai,j为1表示员工i能够制造产...

    02014年4月27日2,174费用流
  • 【网络流24题】航空计划

    【网络流24题】航空计划

    «问题描述:给定一张航空图,图中顶点代表城市,边代表2城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。(1)从最西端城市出发,单向从西向东途经若干城市到达最东端城市,然后再单向从东向西飞回起点(可途经若干城市)。(2)除起点城市外,任何城市只能访问1次。«编程任务:对于给定的航空图,试设计一个算法找出一条满足要求的最佳航空旅行路线。«数据输入:由文件airl.in提供输入数据。文件第1行...

    12014年4月3日1,415费用流
  • 【bzoj3171】[Tjoi2013]循环格

    【bzoj3171】[Tjoi2013]循环格

    DescriptionInput第一行两个整数R,C。表示行和列,接下来R行,每行C个字符LRUD,表示左右上下。Output一个整数,表示最少需要修改多少个元素使得给定的循环格完美SampleInput34RRRDURLLLRRRSampleOutput2HINT1<=R,L<=15题解可知每个点的出度=入度=1二分图+费用流S向每个点连容量1费用0的边每个点拆出的点向T连容量1,费用0的边每个格子向四周连费用0或1的边[crayon-5a12821ec078c259844...

    02014年3月18日1,953费用流