图的连通 - Page 3

「BZOJ1179」[Apio2009] 抢掠计划atm
DescriptionInput第一行包含两个整数N、M。N表示路口的个数，M表示道路条数。接下来M行，每行两个整数，这两个整数都在1到N之间，第i+1行的两个整数表示第i条道路的起点和终点的路口编号。接下来N行，每行一个整数，按顺序表示每个路口处的ATM机中的钱数。接下来一行包含两个整数S、P，S表示市中心的编号，也就是出发的路口。P表示酒吧数目。接下来的一行中有P个整数，表示P个有酒吧的路口的编号Output输出一个...
02014年6月16日6,044spfa,图的连通

「BZOJ1589」[Usaco2008 Dec] Trick or Treat on the Farm 采集糖果
Description每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N(1≤N≤100000)个牛棚里转悠，来采集糖果．她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果．农场不大，所以约翰要想尽法子让奶牛们得到快乐．他给每一个牛棚设置了一个“后继牛棚”．牛棚i的后继牛棚是Xi．他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去，就可以搜集到很多糖果．事实上这是一种有点欺骗意味的手段，来节约他的糖...
02014年6月5日3,970图的连通,记忆化搜索
「BZOJ1529」[POI2005] ska Piggy banks
DescriptionByteazar有N个小猪存钱罐.每个存钱罐只能用钥匙打开或者砸开.Byteazar已经把每个存钱罐的钥匙放到了某些存钱罐里.Byteazar现在想买一台汽车于是要把所有的钱都取出来.他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.Input第一行一个整数N(1<=N<=1.000.000)–表示存钱罐的总数.接下来每行一个整数,第i+1行的整数代表第i个存钱罐的钥匙放置的存钱罐编号.Output一个整数表示最少打破多少个存...
02014年5月17日4,812并查集,图的连通
「BZOJ2208」[JSOI2010] 连通数
DescriptionInput输入数据第一行是图顶点的数量，一个正整数N。接下来N行，每行N个字符。第i行第j列的1表示顶点i到j有边，0则表示无边。Output输出一行一个整数，表示该图的连通数。SampleInput3010001100SampleOutput9HINT对于100%的数据，N不超过2000。题解据说此题暴力是可过的，复杂度O（nm）正解似乎是先缩点完然后递推[crayon-6643240959c3e251962165/] ...
42014年5月15日5,838图的连通
「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,057图的连通
「CODEVS2822」爱在心中
题目描述 Description“每个人都拥有一个梦，即使彼此不相同，能够与你分享，无论失败成功都会感动。爱因为在心中，平凡而不平庸，世界就像迷宫，却又让我们此刻相逢OurHome。”在爱的国度里有N个人，在他们的心中都有着一个爱的名单，上面记载着他所爱的人（不会出现自爱的情况）。爱是具有传递性的，即如果A爱B，B爱C，则A也爱C。如果有这样一部分人，他们彼此都相爱，则他们就超越了一切的限制，用集体的爱化身成为一...
02014年1月26日3,648图的连通
「BZOJ1051」[HAOI2006] 受欢迎的牛
Description每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数(A,B)，表示牛A认为牛B受欢迎。这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。Input第一行两个数N,M。接下来M行，每行两个数A,B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可能出现多个A,B）Output一个数，即有多少头牛被...
42014年1月8日10,071图的连通