图论 - Page 7 - hzwer.com

「BZOJ2303」[Apio2011] 方格染色
DescriptionSam和他的妹妹Sara有一个包含n×m个方格的表格。她们想要将其的每个方格都染成红色或蓝色。出于个人喜好，他们想要表格中每个2× 2的方形区域都包含奇数个（1个或3个）红色方格。例如，右图是一个合法的表格染色方案（在打印稿中，深色代表蓝色，浅色代表红色）。可是昨天晚上，有人已经给表格中的一些方格染上了颜色！现在Sam和Sara非常生气。不过，他们想要知道是否可能给剩下的方格染上颜色，使得整个表格仍...
12015年4月14日7,414并查集

UOJ Easy Round #1
http://vfleaking.blog.uoj.ac/blog/15uoj题解写的太好了。。。「UER#1」猜数[crayon-674358d464620023319557/]「UER#1」跳蚤OS[crayon-674358d464628656878724/]「UER#1」DZYLovesGraph[crayon-674358d46462f155893211/] ...
02015年4月13日6,751并查集,AC自动机
「codechef」April Challenge 2015
BROKPHON模拟[crayon-674358d464ac2709131329/]CHEFLCM所有约数和[crayon-674358d464acc543098087/]PIANO1暴力TT[crayon-674358d464ad0793794776/]CSEQl~r之间每个数的使用次数当作一个变量。。那么就相当于求方程组sigma(xi)(l<=i<=r)=n的非负整数解数。。然后就是排列组合求和[crayon-674358d464ad4988672484/]CARLOS先用并查集将能够相互转化的并在一起dpf(i,j)表示前i个末尾为j的最小改...
22015年4月12日4,882递推与动规,模拟,ST表,并查集,排列组合,乘法逆元
「BZOJ3931」[CQOI2015] 网络吞吐量
题意即题解最短路+网络流1A了赞233[crayon-674358d4652bc771785363/]
82015年4月7日5,560STL,dijkstra,最大流
「BZOJ1797」[Ahoi2009] Mincut 最小割
DescriptionA,B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路。设其中第i(1≤i≤M)条道路连接了vi,ui两个中转站，那么中转站vi可以通过该道路到达ui中转站，如果切断这条道路，需要代价ci。现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小。小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题：问题一...
62015年4月7日10,406最小割,图的连通
「BZOJ2095」[POI2010] Bridges
DescriptionYYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海上，风变得十分大，经过每一座桥都有不可避免的风阻碍YYD，YYD十分ddt，于是用泡芙贿赂了你，希望你能帮他找出一条承...
02015年4月4日4,888二分法,最大流,欧拉图
「East!_XVI」九尾妖狐
Background某无良设计师伊泽瑞尔:刀妹太弱了,我们来增强阿狸吧。Description阿狸现在有N个技能,伊泽瑞尔要决定它们是AD技能还是AP技能。因为出装不同,所以当一个技能是AP时,阿狸的爆发增加ap_i,当一个技能是AD时,阿狸的爆发增加ad_i。有些技能配合可以打出伤害加成,这样阿狸的技能就可以被表示为一张无向图。当有关联的两个技能都是AD时,阿狸的爆发增加AD_i,当两个技能都是AP时,阿狸的爆发增加AP_i,当两个技能不...
02015年4月4日4,386最小割
「BC35」DZY Loves Topological Sorting
问题描述一张有向图的拓扑序列是图中点的一个排列，满足对于图中的每条有向边(u→v)从u到v，都满足u在排列中出现在v之前。现在，DZY有一张有向无环图(DAG)。你要在最多删去k条边之后，求出字典序最大的拓扑序列。输入描述输入有多组数据。(TestCase≤5)第一行，三个正整数n,m,k(1≤n,m≤105,0≤k≤m).接下来m行，每行两个正整数u,v(u≠v,1≤u,v≤n),代表一条有向边(u→v).输出描述对于每组测试数据，输出一行字典序最大的拓...
02015年3月30日3,269STL,贪心,拓扑排序
「BZOJ3894」文理分科
Description 文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：1．如果第i行第秒J的同学选择了文科，则他将获得art[i][j]的满意值，如果选择理科，将得到science[i][j]的满意值。2．如果第i行...
22015年3月25日7,695最小割
「BZOJ1283」序列
Description给出一个长度为的正整数序列Ci，求一个子序列，使得原序列中任意长度为的子串中被选出的元素不超过K(K,M<=100)个，并且选出的元素之和最大。Input第1行三个数N,m,k。接下来N行，每行一个字符串表示Ci。Output最大和。SampleInput10534446666644SampleOutput30HINT20%的数据:n<=10。100%的数据：N<=1000，k,m<=100。Ci<=20000。题解线性规划裸题复习模板ing题解请看：http://hzwer.c...
02015年3月25日4,887费用流
[JSOI2010] 旅行
给定一张无向图,可以k次交换两条边边权，求1到n的最短路交换执行于求最短路之前，边权1<=c<=1000点数<=50边数<=150k<=20此题找不到题解求神犇留言做法我的想法。。。先求从1-n，无视i条边边权的最短路，然后在路径外找i条最短的加回去。。最后只对了5个点。。。[crayon-674358d467bbc684470552/] ...
22015年3月23日3,861STL,spfa
「codechef」March Challenge 2015
只做了前6题弃疗了感觉codechef写题解也没啥人看……「codechefCNOTE」ChefandNotebooks纯模拟[crayon-674358d46837b338967387/]「codechefSIGNWAVE」SignWave听说此题打表可以找规律。。引用zld神犇的话吧。。。就是若干个余弦函数的零点均不同。。然后sin函数的分布就十分奇怪了。。比如s=3的时候就是312131213，忽略两端的情况。。就变成非常规则的1213121然后我们再考虑余弦函数当c=2的时候分布就是011101110...
02015年3月17日3,401模拟,二分法,并查集,离线处理