图论 - Page 11 - hzwer.com

「CF498C」Array and Operations
Youhavewrittenonapieceofpaperanarrayofnpositiveintegersa[1], a[2], ..., a[n]andmgoodpairsofintegers(i1, j1), (i2, j2), ..., (im, jm).Eachgoodpair(ik, jk)meetsthefollowingconditions:ik + jkisanoddnumberand1 ≤ ik < jk ≤ n.Inoneoperationyoucanperformasequenceofactions:takeoneofthegoodpairs(ik, jk)andsomeintegerv(v > 1),whichdividesbothnumbersa[ik]anda[jk];dividebothnum...
02014年12月25日4,426最大流

「BZOJ1486」[HNOI2009] 最小圈
题解分数规划，二分答案用dfs版的spfa判负环[crayon-67438fd753916786904713/]
02014年12月23日5,867spfa,二分法
「BZOJ1922」[SDOI2010] 大陆争霸
Description在一个遥远的世界里有两个国家：位于大陆西端的杰森国和位于大陆东端的克里斯国。两个国家的人民分别信仰两个对立的神：杰森国信仰象征黑暗和毁灭的神曾·布拉泽，而克里斯国信仰象征光明和永恒的神斯普林·布拉泽。幻想历8012年1月，杰森国正式宣布曾·布拉泽是他们唯一信仰的神，同时开始迫害在杰森国的信仰斯普林·布拉泽的克里斯国教徒。幻想历8012年3月2日，位于杰森国东部小镇神谕镇的克里斯国教徒发动起义。幻想...
22014年12月22日6,058STL,dijkstra
「BZOJ2718 / 1143」[Violet 4] 毕业旅行
DescriptionInputOutput最多可选多少景点SampleInput76122354433667SampleOutput2HINT题解最长反链=最小路径覆盖。。。至于证明。。。百度vfk的博客floyd传递闭包后，用n-二分图最大匹配数即为答案[crayon-67438fd754330667036782/] ...
02014年12月22日4,859floyd,最大流
「BZOJ1449 / 2895」[JSOI2009] 球队收益
Description在一个篮球联赛里，有n支球队，球队的支出是和他们的胜负场次有关系的，具体来说，第i支球队的赛季总支出是Ci*x^2+Di*y^2，Di<=Ci。(赢得多，给球员的奖金就多嘛)其中x,y分别表示这只球队本赛季的胜负场次。现在赛季进行到了一半，每只球队分别取得了a[i]场胜利和b[i]场失利。而接下来还有m场比赛要进行。问联盟球队的最小总支出是多少。Input第一行n，m接下来n行每行4个整数a[i],b[i],Ci,Di再接下来m行每行...
22014年12月21日4,677费用流
「POJ3237」Tree
DescriptionYouaregivenatreewithNnodes.Thetree’snodesarenumbered1throughNanditsedgesarenumbered1throughN−1.Eachedgeisassociatedwithaweight.Thenyouaretoexecuteaseriesofinstructionsonthetree.Theinstructionscanbeoneofthefollowingforms:CHANGEivChangetheweightoftheithedgetovNEGATEabNegatetheweightofeveryedgeonthepathfromatobQUERYabFindthemaximumweightofedgesonthepathfromat...
02014年12月21日5,993线段树,树链剖分
「BZOJ1924」[SDOI2010] 所驼门王的宝藏
「问题描述」==============================================================在宽广的非洲荒漠中,生活着一群勤劳勇敢的羊驼家族。被族人恭称为“先知”的AlpacaL.Sotomon是这个家族的领袖,外人也称其为“所驼门王”。所驼门王毕生致力于维护家族的安定与和谐,他曾亲自率军粉碎河蟹帝国主义的野蛮侵略,为族人立下赫赫战功。所驼门王一生财宝无数,但因其生性节俭低调,他将财宝埋藏在自己设计的地下宫殿里,这也是今天HenryCurt...
02014年12月20日6,172递推与动规,STL,图的连通
「BZOJ2438」[中山市选2011] 杀人游戏
Description一位冷血的杀手潜入Na-wiat，并假装成平民。警察希望能在N个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁是杀手，谁是平民。假如查证的对象是杀手，杀手将会把警察干掉。现在警察掌握了每一个人认识谁。每一个人都有可能是杀手，可看作他们是杀手的概率是相同的。问：根据最优的情况，保证警察自身安全并知道谁是杀手的概率最大是多少？Input第一行有两...
32014年12月20日5,927图的连通
「图论练习」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,499图的连通
「图论练习」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,586图的连通
「BZOJ2199」[Usaco2011 Jan] 奶牛议会
Description由于对FarmerJohn的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。议会以“每头牛都可以获得自己想要的”为原则，建立了下面的投票系统：M只到场的奶牛(1<=M<=4000)会给N个议案投票(1<=N<=1,000)。每只奶牛会对恰好两个议案B_iandC_i(1<=B_i<=N;1<=C_i<=N)投出“是”或“否”（输入文件中的'Y'和'N'）。他们的投票结果分别为VB_i(VB_iin{'Y','N'})andVC_i(VC...
12014年12月19日5,1812-SAT
NOI2009植物大战僵尸
DescriptionInputOutput仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。SampleInput32100200-100-51001001211000SampleOutput25HINT在样例中,植物P1,1可以攻击位置(0,0),P2,0可以攻击位置(2,1)。一个方案为，首先进攻P1,1,P0,1，此时可以攻击P0,0。共得到能源收益为(-5)+20+10=25。注意,位置(2,1)被植物P2,0保护，所以无法攻击第2行中的任何植物。「大致数据规...
02014年12月17日6,520最小割,拓扑排序