图的连通 - Page 2

「BZOJ2438」[中山市选2011] 杀人游戏
Description一位冷血的杀手潜入Na-wiat，并假装成平民。警察希望能在N个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？Input第一行有两...
32014年12月20日5,660图的连通

「图论练习」medium
hzwer蒟蒻刚刚学了点图论，现在他面对一张无向连通图他想问你最少添加多少条边，使得任意两点之间有两条无公共边的路（可以有公共点）输入格式第一行n，m，n个点m条边接下来m行，每行u，v表示u到v之间有一条无向边（可能重复描述一条边）输出格式一行，答案样例输入551223344545样例输出1 数据范围20%的数据N<=20,M<=5040%的数据N<=2000,M<=200070%的数据N<=20000,M<=20000100%的数据N&...
42014年12月20日3,230图的连通
「图论练习」easy
hzwer蒟蒻刚刚学了点图论，现在他面对一张有向图他想问你：1：最少选择多少个点，使得从这些点出发能遍历完整个图2：最少添加多少条有向边，能使得整个图成为强连通图输入格式第一行n，m，n个点m条边接下来m行，每行u，v表示一条u到v的有向边输出格式两行，分别为两问答案样例输入53122334样例输出22 数据范围20%的数据N<=20,M<=5040%的数据N<=2000,M<=2000070%的数据N<=5000,M<=5000010...
12014年12月20日4,225图的连通
「BZOJ2893」征服王
Description虽然春希将信息传递给了雪菜，但是雪菜却好像完全不认得春希了。心急如焚的春希打开了第二世代机能，对雪菜的脑内芯片进行了直连-hack。进入到雪菜内部的春希发现（这什么玩意。。），雪菜的脑部结构被分成了n个块落，并且一些块落之间被有向边连接着。由于四分五裂的脑部，雪菜关于春希的记忆也完全消失，春希为了恋人，启动了inversionprocess.在inversionprocess中，要想使雪菜回到正常状态，需要纳米机器人的帮助。...
02014年12月16日4,985费用流,图的连通
「BZOJ2427」[HAOI2010] 软件安装
Description现在我们的手头有N个软件，对于一个软件i，它要占用Wi的磁盘空间，它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上，使得这些软件的价值尽可能大（即Vi的和最大）。但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件j（包括软件j的直接或间接依赖）的情况下才能正确工作（软件i依赖软件j)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够...
42014年12月13日6,215树形动规,图的连通
「BZOJ2730」[HNOI2012] 矿场搭建
Description煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。Input输入文件有若干组数据，每组数据的第一行是一个正整数N（N≤500）...
12014年11月13日5,833图的连通
「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≤...
22014年10月8日7,218递推与动规,拓扑排序,图的连通
「NOIP模拟赛」交通
黄金大神国的首都位于hzwer河中的一座岛屿。一道上班的时候，成千上万辆汽车通过岛屿从西岸的住宅区（由桥连接岛的西部）到东岸的工业区（由桥连接岛的东部）。该岛类似于矩形，它的边平行于主方向。故可将它看作是笛卡尔坐标系中的一个A*B的矩形，它的对角分别为（0,0）和（A,B）。岛上有n个交通节点（后宫建筑），编号为1…n，第i个节点坐标为(xi,yi)。如果一个节点的坐标为(0,y)，它就位于岛的西岸。类似的，坐标为(A,y)的...
02014年9月27日3,208树形动规,图的连通
「CF467D」Fedor and Essay
AfteryouhadhelpedFedortofindfriendsinthe«CallofSoldiers3»game,hestoppedstudyingcompletely.Today,theEnglishteachertoldhimtoprepareanessay.Fedordidn'twanttopreparetheessay,soheaskedAlexforhelp.AlexcametohelpandwrotetheessayforFedor.ButFedordidn'tliketheessayatall.NowFedorisgoingtochangetheessayusingthesynonymdictionaryoftheEnglishlanguage.Fedordoesnotwanttochangethemeaningoftheessa...
02014年9月19日3,041树形动规,图的连通
「BZOJ3391」[Usaco2004 Dec] Tree Cutting网络破坏
Description 约翰意识到贝茜建设网络花费了他巨额的经费，就把她解雇了．贝茜很愤怒，打算狠狠报复．她打算破坏刚建成的约翰的网络．约翰的网络是树形的，连接着N(1≤N≤10000)个牛棚．她打算切断某一个牛棚的电源，使和这个牛棚相连的所有电缆全部中断．之后，就会存在若干子网络．为保证破坏够大，每一个子网的牛棚数不得超过总牛棚数的一半,那哪些牛棚值得破坏呢？Input 第1行：一个整数N. 第...
02014年9月10日3,451图的连通
「NOIP模拟赛」上白泽慧音
题目描述在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。当(A,B...
02014年9月10日2,989图的连通
「BZOJ1123」[POI2008] BLO
DescriptionByteotia城市有n个townsm条双向roads.每条road连接两个不同的towns,没有重复的road.所有towns连通。Input输入n<=100000m<=500000及m条边Output输出n个数，代表如果把第i个点去掉，将有多少对点不能互通。SampleInput551223133445SampleOutput8816148HINTtarjan求割点把某个割点去掉以后，会出现几个连通块，它们之间不能互相到达即会分成上面一棵树，下面若干子树子树之间不互通，所有子树和上面那个...
02014年9月8日16,262图的连通