图论 - Page 6 - hzwer.com

「SPOJ104」Highways
DescriptionInsomecountriesbuildinghighwaystakesalotoftime...Maybethat'sbecausetherearemanypossiblitiestoconstructanetworkofhighwaysandengineerscan'tmakeuptheirmindswhichonetochoose.Supposewehavealistofcitiesthatcanbeconnecteddirectly.Yourtaskistocounthowmanywaystherearetobuildsuchanetworkthatbetweeneverytwocitiesthereexistsexactlyonepath.Twonetworksdifferiftherearetwocitiesthatareconnecteddi...
02015年4月29日3,412矩阵树定理

「BZOJ1194」[HNOI2006] 潘多拉的盒子
DescriptionInput第一行是一个正整数S，表示宝盒上咒语机的个数，（1≤S≤50）。文件以下分为S块，每一块描述一个咒语机，按照咒语机0,咒语机1„„咒语机S－1的顺序描述。每一块的格式如下。一块的第一行有两个正整数n,m。分别表示该咒语机中元件的个数、咒语源输出元的个数（1≤m≤n≤50）。接下来一行有m个数，表示m个咒语源输出元的标号（都在0到n-1之间）。接下来有n行，每一行两个数。第i行（0≤i≤n-1）的两个数表示pi...
02015年4月28日5,142深度搜索,图的连通
「BZOJ3206」[Apio2013] 道路费用
DescriptionInput你的程序必须从标准输入读入。第一行包含三个由空格隔开的整数N，M和K。接下来的 M行描述最开始的M 条道路。这M行中的第i行包含由空格隔开的整数ai，bi和ci，表示有一条在ai和bi之间，费用为ci的双向道路。接下来的K行描述新建的K条道路。这 K行中的第i行包含由空格隔开的整数 xi和yi，表示有一条连接城镇xi和yi新道路。最后一行包含N个由空格隔开的整数，其中的第j个为pj，表示从城镇j 前往城镇...
02015年4月27日6,646kruskal,深度搜索
「BZOJ3700」「FJ2014集训」发展城市
Description 众所周知，Hzwer学长是一名高富帅，他打算投入巨资发展一些小城市。Hzwer打算在城市中开N个宾馆，由于Hzwer非常壕，所以宾馆必须建在空中，但是这样就必须建立宾馆之间的连接通道。机智的Hzwer在宾馆中修建了N-1条隧道，也就是说，宾馆和隧道形成了一个树形结构。Hzwer有时候会花一天时间去视察某个城市，当来到一个城市之后，Hzwer会分析这些宾馆的顾客情况。对于每个顾客，Hzwer用三个数值描述他：（S，...
32015年4月26日5,090最近公共祖先
「BZOJ3624」[Apio2008] 免费道路
DescriptionInputOutputSampleInput572130451320531430121421 SampleOutput320430531121题解优先加1做生成树，得出必须添加的0的边反过来，将0的边加至K条，再放1的边[crayon-674330666db1b324926708/] ...
02015年4月24日5,301贪心,并查集
「BZOJ3996」[TJOI2015] 线性代数
Description给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得D=（A*B-C）*A^T最大。其中A^T为A的转置。输出DInput第一行输入一个整数N，接下来N行输入B矩阵，第i行第J个数字代表Bij.接下来一行输入N个整数，代表矩阵C。矩阵B和矩阵C中每个数字都是不超过1000的非负整数。Output输出最大的DSampleInput3121310123237SampleOutput2HINT 1<=N<=500题解倒腾下式子发现是...
02015年4月22日5,983最小割
「BZOJ3572」[HNOI2014] 世界树
Description 世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。世界树的形态可以用一个数学模型来描述：世界树中有n个种族，种族的编号分别从1到n，分别生活在编号为1到n的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连，道路的长度为1。保...
22015年4月21日11,009虚树,树形动规
「BZOJ1095」[ZJOI2007] Hide 捉迷藏
Description捉迷藏Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激...
72015年4月20日24,861STL,线段树,点分治,最近公共祖先
「BZOJ3991」[SDOI2015] 寻宝游戏
Description 小B最近正在玩一个寻宝游戏，这个游戏的地图中有N个村庄和N-1条道路，并且任何两个村庄之间有且仅有一条路径可达。游戏开始时，玩家可以任意选择一个村庄，瞬间转移到这个村庄，然后可以任意在地图的道路上行走，若走到某个村庄中有宝物，则视为找到该村庄内的宝物，直到找到所有宝物并返回到最初转移到的村庄为止。小B希望评测一下这个游戏的难度，因此他需要知道玩家找到所有宝物需要行走的最短路程。但是这个...
82015年4月17日9,159虚树,dfs序,STL,最近公共祖先
「BZOJ3638 / 3272」Cf172 k – Maximum Subsequence Sum
Description给一列数，要求支持操作：1.修改某个数的值2.读入l,r,k，询问在[l,r]内选不相交的不超过k个子段，最大的和是多少。InputThefirstlinecontainsintegern(1 ≤ n ≤ 105),showinghowmanynumbersthesequencehas.Thenextlinecontainsnintegersa1, a2, ..., an(|ai| ≤ 500).Thethirdlinecontainsintegerm(1 ≤ m ≤ 105)—thenumberofqueries.Thenextmlinescontainthequeriesintheformat,giveninthestate...
22015年4月16日5,011费用流,线段树
TCO 2015 Round 1A DIV1
250：枚举l-r的数，爆搜，统计数位，用map存一下TT实际上对于每个数小范围暴力即可TT[crayon-6743306670494608273450/]500：暴力走min(n^2,K)次，预处理出哪些不能同时取。。。再暴搜+快速幂算方案TAT结果有个点T了。。。正解假如k步之前在一起了，那么k步的时候一定在一起了所以如果我们能求出k步的状态，就可以用每个数出现的次数+1的乘积作为答案（可以选择任意数量的放，也可以不放）所以暴力求状态后乘起来就行了。。...
02015年4月15日33,945STL,深度搜索,二分图匹配
UOJ Round #2
http://vfleaking.blog.uoj.ac/blog/38「UR#2」猪猪侠再战括号序列猪猪侠大神太厉害了[crayon-674330667099e214778604/]下面俩题怎么这么恶心TT「UR#2」跳蚤公路负环能影响一个点v当其与1，v都连通，这个用floyd就好不等式取整要手写虽然分析了那个式子写起来还是蛋疼每个环每个系数k，枚举j，取整范围求并就能得出所能影响的点的x取值范围，x<=l或x>=r一个点的x被许多这样的取整范围限定TT将区间排序一下扫一遍得去...
52015年4月15日4,305贪心,spfa,点分治,floyd