Description In an effort to better manage the grazing patterns of his cows, Farmer John has installed one-way cow paths all over his farm. The farm consists of N fields, conveniently number...
最短路
完全背包问题 题解【有后效性的DP】【最短路】【背包】【同余】
后效性处理+背包合法性转化…又是玄学操作,不过感觉对DP的理解又深入了一些。 题目描述 有\(n\)种物品,物品的体积分别为\(V_1,V_2,\dots,V_n\),且每种物品的数量都可以看做是无限多的...
AT3621 ARC084D Small Multiple 题解【01BFS】【同余】
把一个数学题建成一个图论题 Problem Statement Find the smallest possible sum of the digits in the decimal notation of a positive multiple of \(K\). Constrai...
洛谷 P1606 [USACO07FEB]荷叶塘Lilypad Pond 题解【最短路计数】【构造】
毒瘤的建图方式…… 题目描述 FJ has installed a beautiful pond for his cows' aesthetic enjoyment and exercise. The rectangular pond has been partitioned into square ce...
洛谷 P1653 猴子 题解【并查集】【最短路】
这个一年前开坑的题到现在终于解决了…… 题目描述 有N只猴子,第一只尾巴挂在树上,剩下的N-1只,要么被其他的猴子抓住,要么抓住了其他的猴子,要么两者均有。当然一只猴子最多抓两...
洛谷 P1979 NOIp2013提高组 华容道 题解【最短路】【构造】
毒瘤图论建模题 题目描述 小B最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程来完成华容道:给定一种局面, 华容道是否根本就无法完成,如果能完成, ...
洛谷 P2446 [SDOI2010]大陆争霸 题解【优先队列bfs】【最短路】【贪心】
本来思路对了但是转移写麻烦了把自己绕进去了。 题目背景 在一个遥远的世界里有两个国家:位于大陆西端的杰森国和位于大陆东端的克里斯国。两个国家的人民分别信仰两个对立的神:杰...
NOIp2014提高组 P2296 寻找道路 题解【图论】【最短路】【搜索】
思路简单但是细节很多的一道题。 题目描述 Description 在有向图G中,每条边的长度均为1,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件: &...
洛谷 P1730 最小密度路径 题解【Floyd】【DP】
Floyd的一个简单变形。 题目描述 给出一张有N个点M条边的加权有向无环图,接下来有Q个询问,每个询问包括2个节点X和Y,要求算出从X到Y的一条路径,使得密度最小(密度的定义为,路径...
洛谷 P2498 [SDOI2012]拯救小云公主 题解【最短路】【贪心】【构造】【生成树】
这种题是用SPFA优化的?? 题目描述 英雄又即将踏上拯救公主的道路…… 这次的拯救目标是——爱和正义的小云公主。 英雄来到boss的洞穴门口,他一下子就懵了...