图论 - Page 16 - hzwer.com

「BZOJ3402」[Usaco2009 Open] Hide and Seek 捉迷藏
Description 贝茜在和约翰玩一个“捉迷藏”的游戏．她正要找出所有适合她躲藏的安全牛棚．一共有N(2≤N≤20000)个牛棚，被编为1到N号．她知道约翰（捉牛者）从牛棚1出发．所有的牛棚由M(1≤M≤50000)条双向路连接，每条双向路连接两个不同的牛棚．所有的牛棚都是相通的．贝茜认为同牛棚1距离最远的的牛棚是安全的．两个牛棚间的距离是指，从一个牛棚到另一个牛棚最少需要通过的道路数量．请帮贝茜找出所有的安...
02014年9月26日3,773dijkstra

「BZOJ2555」SubString
Description懒得写背景了，给你一个字符串init，要求你支持两个操作(1):在当前字符串的后面插入一个字符串(2):询问字符串s在当前字符串中出现了几次？(作为连续子串)你必须在线支持这些操作。Input 第一行一个数Q表示操作个数第二行一个字符串表示初始字符串init接下来Q行，每行2个字符串Type,StrType是ADD的话表示在后面插入字符串。Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。为了体现在...
02014年9月25日9,120后缀自动机,link cut tree
「POJ1734」Sightseeing trip
DescriptionThereisatravelagencyinAdeltontownonZanzibarisland.Ithasdecidedtoofferitsclients,besidesmanyotherattractions,sightseeingthetown.Toearnasmuchaspossiblefromthisattraction,theagencyhasacceptedashrewddecision:itisnecessarytofindtheshortestroutewhichbeginsandendsatthesameplace.Yourtaskistowriteaprogramwhichfindssucharoute.InthetownthereareNcrossingpointsnumberedfrom1toNandMtwo-wayr...
02014年9月24日4,088floyd
「BZOJ3706」「FJ2014集训」反色刷
「题目描述」给一张无向图，边有黑白两种颜色，现在你有一堆反色刷，可以从任意点开始刷，经过若干条边后回到起点。现在要询问至少需要多少个反色刷可以使这张图所有边都变成白色。因为某种原因，边的颜色是会改变的，于是。。需要支持以下操作：1x把第x条边反色（编号从0~m-1）2 询问当前图中最少需要多少个反色刷「输入格式」第一行两个整数nm表示这张图有n个点m条边接下来m行每行3个整数uvc表示一条无向边和这条边的颜色(0为...
02014年9月24日4,123欧拉图
「CF467D」Fedor and Essay
AfteryouhadhelpedFedortofindfriendsinthe«CallofSoldiers3»game,hestoppedstudyingcompletely.Today,theEnglishteachertoldhimtoprepareanessay.Fedordidn'twanttopreparetheessay,soheaskedAlexforhelp.AlexcametohelpandwrotetheessayforFedor.ButFedordidn'tliketheessayatall.NowFedorisgoingtochangetheessayusingthesynonymdictionaryoftheEnglishlanguage.Fedordoesnotwanttochangethemeaningoftheessa...
02014年9月19日3,577树形动规,图的连通
「BZOJ3282」Tree
Description给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变...
22014年9月18日6,037link cut tree
「BZOJ3514」Codechef MARCH14 GERALD07加强版
DescriptionN个点M条边的无向图，询问保留图中编号在[l,r]的边的时候图中的联通块个数。Input第一行四个整数N、M、K、type，代表点数、边数、询问数以及询问是否加密。接下来M行，代表图中的每条边。接下来K行，每行两个整数L、R代表一组询问。对于type=0的测试点，读入的L和R即为询问的L、R；对于type=1的测试点，每组询问的L、R应为Lxorlastans和Rxorlastans。Output K行每行一个整数代表该组询问的联通块...
32014年9月11日8,226主席树,link cut tree
「BZOJ3391」[Usaco2004 Dec] Tree Cutting网络破坏
Description 约翰意识到贝茜建设网络花费了他巨额的经费，就把她解雇了．贝茜很愤怒，打算狠狠报复．她打算破坏刚建成的约翰的网络．约翰的网络是树形的，连接着N(1≤N≤10000)个牛棚．她打算切断某一个牛棚的电源，使和这个牛棚相连的所有电缆全部中断．之后，就会存在若干子网络．为保证破坏够大，每一个子网的牛棚数不得超过总牛棚数的一半,那哪些牛棚值得破坏呢？Input 第1行：一个整数N. 第...
02014年9月10日4,113图的连通
「NOIP模拟赛」上白泽慧音
题目描述在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。当(A,B...
02014年9月10日3,723图的连通
「BZOJ1123」[POI2008] BLO
DescriptionByteotia城市有n个townsm条双向roads.每条road连接两个不同的towns,没有重复的road.所有towns连通。Input输入n<=100000m<=500000及m条边Output输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。SampleInput551223133445SampleOutput8816148HINTtarjan求割点把某个割点去掉以后，会出现几个连通块，它们之间不能互相到达即会分成上面一棵树，下面若干子树子树之间不互通，所有子树和上面那个...
02014年9月8日17,382图的连通
「BZOJ3479」[Usaco2014 Mar] Watering the Fields
Description Duetoalackofrain,FarmerJohnwantstobuildanirrigationsystemtosendwaterbetweenhisNfields(1<=N<=2000).Eachfieldiisdescribedbyadistinctpoint(xi,yi)inthe2Dplane,with0<=xi,yi<=1000.ThecostofbuildingawaterpipebetweentwofieldsiandjisequaltothesquaredEuclideandistancebetweenthem:(xi-xj)^2+(yi-yj)^2FJwouldliketobuildaminimum-costsystemofpipessothatallofhisfieldsarelinkedt...
02014年9月7日3,480prim
「BZOJ2599」[IOI2011] Race
Description给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.Input第一行两个整数n,k第二..n行每行三个整数表示一条无向边的两端和权值(注意点的编号从0开始)Output一个整数表示最小边数量如果不存在这样的路径输出-1SampleInput43011122134SampleOutput2题解这题有点怪的点分治。。。我的做法也比较逗，就是开一个100W的数组t,t[i]表示权值为i的路径最少边数找到重心分成若干子树后，得出一棵子树的所有点到...
22014年9月7日8,345点分治