Orangeko

未归档

技术笔记(2) 题解(3)

/ 注册

全部文章 / 未归档（共139篇）

P1546 最短网络 Agri-Net【MST】

题目背景 Farmer John 被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。题目描述 FJ 已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场...

最小生成树

2020-03-01

0 542

P3225 [HNOI2012]矿场搭建【割点 + 求点双 + 简单组合数】

展开题目描述煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来...

强连通

2020-02-29

0 540

P3119 [USACO15JAN]Grass Cownoisseur G [ Tarjan + 缩点 + 拓扑序 + dp + 最长路] [好题]

题目描述 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 consi...

最短路强连通 dp

2020-02-29

0 548

P2746 [USACO5.3]校园网Network of Schools [tarjan缩点]

题目描述一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 BB 在 AA 学校的分发列表中，AA 也不一定在 BB 学校的列表中。你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最...

强连通

2020-02-28

0 486

P1196 [NOI2002]银河英雄传说【带权并查集】

思路　　用sum记录每个舰队的战舰数量， tohead 记录当前舰离舰首的距离，那么求任意两舰之间有多少舰显然就是 abs( tohead[i] - tohead[j] ) - 1； CODE 1 #include <bits/s...

并查集

2020-02-28

0 536

P1197 [JSOI2008]星球大战 [删边求连通块个数]

展开题目描述很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快帝国又重新造出了他...

并查集

2020-02-28

0 631

P2024 NOI2001 种类冰茶鸡

展开题目描述动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B 吃 C，C 吃 A。现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这...

并查集

2020-02-27

0 509

P1111 修复公路

题目背景 AA地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。题目描述给出A地区的村庄数NN，和公路数MM，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意...

并查集

2020-02-27

0 559

P1613 跑路【倍增】【最短路】

题目描述小A的工作不仅繁琐，更有苛刻的规定，要求小A每天早上在6：00之前到达公司，否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资，小A买了一个十分牛B的空间跑路器，每秒钟可以跑2^k千米（k是任意自然数）。当然，这个机器是用longint存的，所以总跑路长度不能...

倍增最短路

2020-02-27

0 484

P1967 货车运输【LCA】【生成树】

题目描述 A 国有 nn 座城市，编号从 11 到 nn，城市之间有 mm 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 qq 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。输入格式第一行有两个用一个空格隔开的整数 ...

LCA

2020-02-26

0 510