图论

HDU 6023 ping ping ping

Time Limit: 2000/1000 MS (Java/Others) LCA + 贪心 The structure of the computer room in Northeastern University is pretty miraculous. There are $ n$ servers, some servers connect to the gateway whose $ IP$ address is $ 0$ directly. All servers are connected with each other by $ n$ netting twines. It is said that this structure is favorable for maintaining physical problem of servers. (更多…)

luoyayu
数论

HDU 6129 Just do it

记一次打表没看出规律 Time Limit: 5000/2500 MS (Java/Others) There is a nonnegative integer sequence $ a_1...n$ of length $ n$. HazelFan wants to do a type of transformation called prefix-XOR, which means a1...n changes into b1...n, where bi equals to the $ XOR$ value of $ a_1,...,a_i$. He will repeat it for $ m$ times, please tell him the final sequence. (更多…)

luoyayu
图论

HDU 6121 Build a tree

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

Problem Description

HazelFan wants to build a rooted tree. The tree has $ n$ nodes labeled $ 0$ to $ n−1$, and the father of the node labeled $ i$ is the node labeled$ \lfloor\frac{i-1}{k}\rfloor$. HazelFan wonders the size of every subtree, and you just need to tell him the $ XOR$ value of these answers. (更多…)

luoyayu
LCA

LCA

最近学了LCA的相关问题在此总结下

在有根树中,两个节点u和v的公共祖先中距离最近的那个成为其最近公共祖先,在树上两点因为存在唯一的最短路,故其LCA为最短路上深度最小的点。通过求解LCA我们可以处理如求解树或DAG上任意两点的最短距离,将RMQ转化为LCA,结合树链剖分操作等。 求解$LCA$的各种方法全部以HDU 2586为例(自娱自乐) (更多…)

luoyayu
图论

Maximum Weight Closure of a Graph

今天做题遇到了这个经典问题,拜读了《最小割模型在信息学竞赛中的应用》也顺便回顾下网络流的相关知识。全文当作是对论文的回顾,同时感谢作者的辛勤付出。

Introduction

最大权闭合图指的是一个有向图$G=(V,E)$的点集$V$,且该点集满足如果$u$在$V$中,那么$u$指向的后继$v$也在$V$中,给每个点分配一个权值(可正可负),那么最大的权闭合子图就是点权最大的闭合图。 (更多…)

luoyayu
图论

HDU 4034 Graph

Time Limit: 2000/1000 MS (Java/Others)

Problem Description

Everyone knows how to calculate the shortest path in a directed graph. In fact, the opposite problem is also easy. Given the length of shortest path between each pair of vertexes, can you find the original graph? (更多…)

luoyayu