• 「BZOJ2427」[HAOI2010] 软件安装

     「BZOJ2427」[HAOI2010] 软件安装

    Description现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够...

    52014年12月13日3,644树形动规,图的连通
  • 「BZOJ2730」[HNOI2012] 矿场搭建

    「BZOJ2730」[HNOI2012] 矿场搭建

    Description煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。Input输入文件有若干组数据,每组数据的第一行是一个正整数N(N≤500)...

    12014年11月13日4,047图的连通
  • 「BZOJ1093」[ZJOI2007] 最大半连通子图

    「BZOJ1093」[ZJOI2007] 最大半连通子图

    DescriptionInput第一行包含两个整数N,M,X。N,M分别表示图G的点数与边数,X的意义如上文所述。接下来M行,每行两个正整数a,b,表示一条有向边(a,b)。图中的每个点将编号为1,2,3…N,保证输入中同一个(a,b)不会出现两次。Output应包含两行,第一行包含一个整数K。第二行包含整数CModX.SampleInput6620070603122113245664SampleOutput33HINT对于100%的数据,N≤100000,M≤1000000;对于100%的数据,X≤...

  • 「NOIP模拟赛」交通

    「NOIP模拟赛」交通

    黄金大神国的首都位于hzwer河中的一座岛屿。一道上班的时候,成千上万辆汽车通过岛屿从西岸的住宅区(由桥连接岛的西部)到东岸的工业区(由桥连接岛的东部)。该岛类似于矩形,它的边平行于主方向。故可将它看作是笛卡尔坐标系中的一个A*B的矩形,它的对角分别为(0,0)和(A,B)。岛上有n个交通节点(后宫建筑),编号为1…n,第i个节点坐标为(xi,yi)。如果一个节点的坐标为(0,y),它就位于岛的西岸。类似的,坐标为(A,y)的...

    02014年9月27日1,620树形动规,图的连通
  • 「CF467D」Fedor and Essay

    「CF467D」Fedor and Essay

    AfteryouhadhelpedFedortofindfriendsinthe«CallofSoldiers3»game,hestoppedstudyingcompletely.Today,theEnglishteachertoldhimtoprepareanessay.Fedordidn'twanttopreparetheessay,soheaskedAlexforhelp.AlexcametohelpandwrotetheessayforFedor.ButFedordidn'tliketheessayatall.NowFedorisgoingtochangetheessayusingthesynonymdictionaryoftheEnglishlanguage.Fedordoesnotwanttochangethemeaningoftheessa...

    02014年9月19日1,765树形动规,图的连通
  • 「BZOJ3391」[Usaco2004 Dec] Tree Cutting网络破坏

    「BZOJ3391」[Usaco2004 Dec] Tree Cutting网络破坏

    Description    约翰意识到贝茜建设网络花费了他巨额的经费,就把她解雇了.贝茜很愤怒,打算狠狠报复.她打算破坏刚建成的约翰的网络.    约翰的网络是树形的,连接着N(1≤N≤10000)个牛棚.她打算切断某一个牛棚的电源,使和这个牛棚相连的所有电缆全部中断.之后,就会存在若干子网络.为保证破坏够大,每一个子网的牛棚数不得超过总牛棚数的一半,那哪些牛棚值得破坏呢?Input    第1行:一个整数N.    第...

    02014年9月10日1,897图的连通
  • 「NOIP模拟赛」上白泽慧音

    「NOIP模拟赛」上白泽慧音

    题目描述在幻想乡,上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞,使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄(编号为1..N)和M条道路组成,道路分为两种一种为单向通行的,一种为双向通行的,分别用1和2来标记。如果存在由村庄A到达村庄B的通路,那么我们认为可以从村庄A到达村庄B,记为(A,B)。当(A,B...

    02014年9月10日1,369图的连通
  •  「BZOJ1123」[POI2008] BLO

     「BZOJ1123」[POI2008] BLO

    DescriptionByteotia城市有n个townsm条双向roads.每条road连接两个不同的towns,没有重复的road.所有towns连通。Input输入n<=100000m<=500000及m条边Output输出n个数,代表如果把第i个点去掉,将有多少对点不能互通。SampleInput551223133445SampleOutput8816148HINTtarjan求割点把某个割点去掉以后,会出现几个连通块,它们之间不能互相到达即会分成上面一棵树,下面若干子树子树之间不互通,所有子树和上面那个...

    02014年9月8日3,198图的连通
  • 「BZOJ1179」[Apio2009] 抢掠计划atm

    「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日3,764spfa,图的连通
  • 「BZOJ1589」[Usaco2008 Dec] Trick or Treat on the Farm 采集糖果

    「BZOJ1589」[Usaco2008 Dec] Trick or Treat on the Farm 采集糖果

    Description每年万圣节,威斯康星的奶牛们都要打扮一番,出门在农场的N(1≤N≤100000)个牛棚里转悠,来采集糖果.她们每走到一个未曾经过的牛棚,就会采集这个棚里的1颗糖果. 农场不大,所以约翰要想尽法子让奶牛们得到快乐.他给每一个牛棚设置了一个“后继牛棚”.牛棚i的后继牛棚是Xi.他告诉奶牛们,她们到了一个牛棚之后,只要再往后继牛棚走去,就可以搜集到很多糖果.事实上这是一种有点欺骗意味的手段,来节约他的糖...

    02014年6月5日2,345图的连通,记忆化搜索
  • 「BZOJ1529」[POI2005] ska Piggy banks

    「BZOJ1529」[POI2005] ska Piggy banks

    DescriptionByteazar有N个小猪存钱罐.每个存钱罐只能用钥匙打开或者砸开.Byteazar已经把每个存钱罐的钥匙放到了某些存钱罐里.Byteazar现在想买一台汽车于是要把所有的钱都取出来.他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.Input第一行一个整数N(1<=N<=1.000.000)–表示存钱罐的总数.接下来每行一个整数,第i+1行的整数代表第i个存钱罐的钥匙放置的存钱罐编号.Output一个整数表示最少打破多少个存...

    02014年5月17日2,604并查集,图的连通
  • 「BZOJ2208」[JSOI2010] 连通数

    「BZOJ2208」[JSOI2010] 连通数

    DescriptionInput输入数据第一行是图顶点的数量,一个正整数N。接下来N行,每行N个字符。第i行第j列的1表示顶点i到j有边,0则表示无边。Output输出一行一个整数,表示该图的连通数。SampleInput3010001100SampleOutput9HINT对于100%的数据,N不超过2000。题解据说此题暴力是可过的,复杂度O(nm)正解似乎是先缩点完然后递推[crayon-5b281c217f633688959454/] ...

    42014年5月15日3,673图的连通