图论 - Page 23 - hzwer.com

「BZOJ1854」[SCOI2010] 游戏
Descriptionlxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，...
82014年5月8日9,317并查集

「BZOJ3280」小R的烦恼
Description小R最近遇上了大麻烦，他的程序设计挂科了。于是他只好找程设老师求情。善良的程设老师答应不挂他，但是要求小R帮助他一起解决一个难题。问题是这样的，程设老师最近要进行一项邪恶的实验来证明P=NP，这个实验一共持续n天，第i天需要a[i]个研究生来给他搬砖。研究生毕竟也是人，所以雇佣研究生是需要钱的，机智的程设老师已经联系好了m所大学，第j所大学共有l[j]个研究生，同时雇佣这所大学的一个研究生需要p[j]元...
02014年5月8日3,963费用流
「BZOJ1787」[Ahoi2008] Meet 紧急集合
DescriptionInputOutputSampleInput641223244556456631244666SampleOutput52254160HINT题解忘记换行搞半天我擦咧求三个结点到一个结点距离之和最小的结点以及距离和求出两两lca，其中有两个相同，答案则为另一个，画画图就可以理解[crayon-67439c3f066c9304120932/]或者将三个lca分别计算取最优[crayon-67439c3f066d6450871068/] ...
22014年5月7日5,586最近公共祖先
「JoyOI1517」飘飘乎居士的乌龟
背景Background飘飘乎居士养了乌龟。当然，这些乌龟是用来出售赚取利润的。描述Description飘飘乎居士的乌龟被安置在了m个窝中。现在，飘飘乎居士已经接到了n个人的定购通知，他们会按顺序在来挑选乌龟，其中，第i个人会在pi个窝中挑选乌龟，但最多只想买xi只乌龟。另外，在第i个人购买完乌龟以后，飘飘乎居士会将指定的qi个窝中的龟进行调整，他可以任意调换指定的qi个窝中乌龟数量。飘飘乎希望知道，在n个人购买完乌龟后，他最...
02014年5月4日2,663最大流
「CF427C」Checkposts
Yourcityhas n junctions.Thereare m one-way roadsbetweenthejunctions.Asamayorofthecity,youhavetoensurethesecurityofallthejunctions.Toensurethesecurity,youhavetobuildsomepolicecheckposts.Checkpostscanonlybebuiltinajunction.Acheckpostatjunction icanprotectjunction j ifeither i = j orthepolicepatrolcarcangoto j from i andthencomebackto i.Buildingcheckpostscostssomemoney.Assome...
02014年5月3日3,263图的连通
一笔画成
来源：http://218.5.5.242:9018/JudgeOnline/problem.php?id=1442题目描述一个图能否一笔画成，如果能请你每次都从当前最小编号的点开始画起，如果不行，则输出“noanswer”输入40100101101010110输出12342题解诶，这题是无向图。。首先用并查集判断图是否连通，这个略过。。然后图中要有0或2个度为奇数的点如果是0个，则任意一个点都可以为起点，且为终点。2个的话当然一个起点一个终点，dfs输出路径，同时保证每条边只走一次，...
02014年5月2日3,194欧拉图
「BZOJ2879」[Noi2012] 美食节
DescriptionCZ市为了欢迎全国各地的同学，特地举办了一场盛大的美食节。作为一个喜欢尝鲜的美食客，小M自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而，尝鲜的欲望是难以满足的。尽管所有的菜品都很可口，厨师做菜的速度也很快，小M仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小M开始研究起了做菜顺序的问题，即安排一个做菜的顺序使得同学们的等待时间最短。小M发现，美食节...
42014年5月1日7,010费用流
「BZOJ1070」[SCOI2007] 修车
Description同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。Input第一行有两个m,n，表示技术人员数与顾客数。接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的...
122014年5月1日8,571费用流
网络流&费用流模板
网络流dinic[crayon-67439c3f08f5d481942109/]最小费用最大流spfa[crayon-67439c3f08f68054294458/]zkw费用流[crayon-67439c3f08f6f991558659/]
132014年5月1日18,219最小割,费用流,最大流
「BZOJ3275」Number
Description有N个正整数，需要从中选出一些数，使这些数的和最大。若两个数a,b同时满足以下条件，则a,b不能同时被选1:存在正整数C，使a*a+b*b=c*c2:gcd(a,b)=1Input第一行一个正整数n，表示数的个数。第二行n个正整数a1,a2,?an。Output最大的和。SampleInput534567SampleOutput22HINTn<=3000。题解将所有点拆成2个0向i连权为a[i]的边，a[i]向T连权为a[i]的边有关系的点互相连边，权为inf答案是tot-ans/2[crayon-6...
52014年5月1日5,176最小割
「BZOJ2768」[JLOI2010] 冠军调查
Description一年一度的欧洲足球冠军联赛已经进入了淘汰赛阶段。随着卫冕冠军巴萨罗那的淘汰，英超劲旅切尔西成为了头号热门。新浪体育最近在吉林教育学院进行了一次大规模的调查，调查的内容就是关于切尔西能否在今年问鼎欧洲冠军。新浪体育的记者从各个院系中一共抽取了n位同学作为参与者，大家齐聚一堂，各抒己见。每一位参与者都将发言，阐述自己的看法。参与者的心里都有一个看法，比如FireDancer认为切尔西不可能夺冠，而W...
02014年4月30日4,306最小割
「BZOJ1984」月下“毛景树”
Description毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。爬啊爬~爬啊爬~~毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~~~“毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数：Changekw：将第k条树枝上毛毛果的...
02014年4月29日6,151线段树,树链剖分