图论 - Page 13 - hzwer.com

「BZOJ3306」树
Description给定一棵大小为n的有根点权树,支持以下操作:•换根•修改点权•查询子树最小值Input第一行两个整数n,Q,分别表示树的大小和操作数。接下来n行,每行两个整数f,v,第i+1行的两个数表示点i的父亲和点i的权。保证f<i。如果f=0,那么i为根。输入数据保证只有i=1时,f=0。接下来m行,为以下格式中的一种:•Vxy表示把点x的权改为y•Ex表示把有根树的根改为点x•Qx表示查询点x的子树最小值Output对于每个Q,输出子树最小值...
02014年12月11日7,413dfs序,线段树,树上倍增

「BZOJ2929」[POI1999] 洞穴攀行
Description一队洞穴学者在ByteMountain的GrateCave里组织了一次训练。训练中，每一位洞穴学者要从最高的一个室到达最底下的一个室。他们只能向下走。一条路上每一个连续的室都要比它的前一个低。此外，每一个洞穴学者都要从最高的室出发，沿不同的路走到最低的室。问：可以有多少个人同时参加训练？任务：写一个程序：l 读入对洞穴的描述。l 计算可以同时参加训练的人数。l 将...
132014年12月9日4,125最大流
「BZOJ1027」[JSOI2007] 合金
Description某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料，不同种类的原材料中铁铝锡的比重不同。然后，将每种原材料取出一定量，经过融解、混合，得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。现在，用户给出了n种他们需要的合金，以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料，并且使用这些原材料可以加工出用户需要的所有种类的合金。Input第一行两个...
82014年12月9日6,519floyd,几何
WC2010重建计划
DescriptionInput第一行包含一个正整数N，表示X国的城市个数.第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi其中城市由1..N进行标号Output输出最大平均估值，保留三位小数SampleInput423121132143SampleOutput2.500HINT20%的数据,N<=500030%的数据,N<=100000,原有方案恰...
22014年12月3日7,524点分治,二分法,单调队列
WC2013糖果公园
DescriptionInputOutputSampleInputSampleOutput841312784HINT题解30分暴力。。。模拟即可第4-5个测试点由于m较小，且在链上，所以可以用前缀和水过。。。对于每个询问统计每种糖果的答案贡献满分做法带修改树上莫队。。。参见vfk的博客http://vfleaking.blog.163.com/blog/#m=0&t=1&c=fks_084070093085082071086081080095085081085075084081080064080但是vfk的这种树分块方式。。。。。。感觉[B,3B]的话把应...
52014年11月29日9,027莫队算法,最近公共祖先
「BZOJ3757」苹果树
Description神犇家门口种了一棵苹果树。苹果树作为一棵树，当然是呈树状结构，每根树枝连接两个苹果，每个苹果都可以沿着一条由树枝构成的路径连到树根，而且这样的路径只存在一条。由于这棵苹果树是神犇种的，所以苹果都发生了变异，变成了各种各样的颜色。我们用一个到n之间的正整数来表示一种颜色。树上一共有n个苹果。每个苹果都被编了号码，号码为一个1到n之间的正整数。我们用0代表树根。只会有一个苹果直接根。有许许多多的...
02014年11月28日10,073莫队算法,最近公共祖先
「BZOJ2407」探险
Description探险家小T好高兴！X国要举办一次溶洞探险比赛，获奖者将得到丰厚奖品哦！小T虽然对奖品不感兴趣，但是这个大振名声的机会当然不能错过！比赛即将开始，工作人员说明了这次比赛的规则：每个溶洞和其他某些溶洞有暗道相连。两个溶洞之间可能有多条道路，也有可能没有，但没有一条暗道直接从自己连到自己。参赛者需要统一从一个大溶洞出发，并再次回到这个大溶洞。如果就这么点限制，那么问题就太简单了，可是举办方又...
12014年11月27日4,996STL,dijkstra
「BZOJ2259」[Oibh] 新型计算机
DescriptionTim正在摆弄着他设计的“计算机”，他认为这台计算机原理很独特，因此利用它可以解决许多难题。但是，有一个难题他却解决不了，是这台计算机的输入问题。新型计算机的输入也很独特，假设输入序列中有一些数字（都是自然数——自然数包括0），计算机先读取第一个数字S1，然后顺序向后读入S1个数字。接着再读一个数字S2，顺序向后读入S2个数字……依此类推。不过只有计算机正好将输入序列中的数字读完，它才能正确处...
02014年11月25日4,501STL,dijkstra
「BZOJ2730」[HNOI2012] 矿场搭建
Description煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。Input输入文件有若干组数据，每组数据的第一行是一个正整数N（N≤500）...
12014年11月13日6,061图的连通
NOIP2008双栈排序
描述Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。操作a如果输入序列不为空，将第一个元素压入栈S1操作b如果栈S1不为空，将S1栈顶元素弹出至输出序列操作c如果输入序列不为空，将第一个元素压入栈S2操作d如果栈S2不为空，将S2栈顶元素弹出至输出序列如果一个1~n的排列P可以通过一系列操作使得输出序列为1，2，…，(n-1)，n，Tom就称P是一个“可双栈排...
12014年11月6日5,190二分图染色
「NOIP模拟赛」排队
「问题描述」Czy喜欢将他的妹子们排成一队。假设他拥有N只妹纸，编号为1至N。Czy让他们站成一行，等待自己来派送营养餐。这些妹纸按照编号大小排列，并且由于它们都很想早点吃饭，于是就很可能出现多只妹纸挤在同一位置的情况(也就是说，如果我们认为妹纸位于数轴上，那么多只妹纸的位置坐标可能相同)。因为众所周知的原因，某些妹纸之间互相喜欢，他们希望互相之间的距离至多为一个定值。但某些妹纸之间互相厌恶，他们希望互相...
02014年11月5日3,954差分约束
「NOIP模拟赛」感冒病毒
「题目描述」一种感冒病毒正在学校里传播，这所学校有n个学生，m个学生社团，每个学生可能参加了多个社团，因为同一个社团的学生交流较多，所以如果一个学生感染上感冒病毒，那么他所在的社团里的所有学生都会感染上感冒病毒，现在已知0号学生感染上感冒病毒，问现在有多少人会感染上感冒病毒。「输入」输入文件：suspects.in输入的第一行是两个整数n和m，表示学生的数目和社团的数目,学生的编号为0到n-1。接下来m行，每行首先是一...
02014年11月4日2,631并查集