ResurrectionTX

分类

比赛(7) 笔记(6) 题解(32)

/ 注册

全部文章（共9篇）

2020牛客NOIP赛前集训营-提高组（第六场）C 路径难题

wdnmd真就自闭了，上次数组开小1扣了15分痛失阿珂，这次一样扣了15分。对于出租车类型为1的边，连边方式同普通无向图。对于公交车连类型为2的边，建两个虚点1和2，先把所有站点向虚点1连边权为0的单向边，再从虚点1向虚点2连边权为c的单向变，再从虚点2向所有站点连边权为c的单向边。这样每次就...

最短路网络流

2020-10-29

3 590

UVA 1104 【芯片难题 Chips Challenge】

Description 传送门 Solution 因为每一行最多方的芯片数量是随着芯片总数量变化的，这样不好整，所以我们枚举最大数量，用网络流跑出此时最多放置多少芯片如果比我们枚举的最大数量是合法的，就更新答案。建立\(a_i\)表示行，建立\(b_i\)表示列。从\(S\)向\(...

网络流 UVA

2020-06-12

0 423

网络流

最大流 \(Dinic\) 直接上代码CwQwC。 #include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; c...

网络流

2020-06-12

0 492

Luogu P4249 【[WC2007]剪刀石头布】

Description 传送门 Solution 首先发现直接求这种三元组不打好求，那么考虑球不满足这种关系的三元组的数量。注意到一个三元组，如果不满足这种关系，肯定分别赢了\(0\)，\(1\)，\(2\)场。那么我们如果知道了每个人赢的场数\(y_i\)，不具有这种关系的三元组...

网络流 Luogu

2020-06-12

0 348

Luogu P2754 【[CTSC1999]家园 / 星际转移问题】

Description 传送门 Solution 判断有无解可以使用并查集，如果最后地球和月球能处在同一个集合中，那么肯定可以到达，只是时间长短的问题。因为多个飞船是同时飞行的，这样的问题不好直接处理。考虑星球的个数特别少，这时可以考虑按照时间轴建立分层图，\(S\)向每个时间点的地球...

分层图网络流并查集 Luogu

2020-06-12

0 386

Luogu P4313 【文理分科】

Description 传送门 Solution 每个点只有两种选择，不是选文科就是选理科，从\(S\)向每个同学连容量为选文科的满意值的有向边，从每个同学向\(T\)连容量为选理科的满意值的有向边，那么总的满意值减去最小割就是答案。现在考虑如何在所有相邻的同学选同一个课时增加满意值，...

网络流 Luogu

2020-06-12

0 341

Luogu P1646 【[国家集训队]happiness】

Description 传送门 Solution 一种列方程的套路。我们先单独找出两个点的关系来考虑。假设有\(x\)和\(y\)两个同学，向\(S\)连边代表选理科，向\(T\)连边代表选文科。设\(S\)向\(x\)连的有向边为\(a\)，\(S\)向\(y\)连的有向边为\(...

网络流 Luogu

2020-06-12

0 419

Luogu P4174 【[NOI2006]最大获利】

Description 传送门 Solution 经典的最大权闭合子图问题。首先\(S\)向每个中转站连容量为费用的有向边。每个群体向\(T\)连容量为收益的有向边。如果一个中转站的点被割了，那么相当于建立这个中转站；如果一个群体被割了相当于不选这个群体。那么答案就是所有群...

网络流 Luogu

2020-06-12

0 348

Luogu P4311 【士兵占领】

Description 传送门 Solution 首先如果士兵只能给一行或一列造成贡献的答案是\(\sum_{i = 1}^m l_i + \sum_{i = 1}^n c_i\)。但是发现有的士兵可以同时给一列和一行造成贡献。那就算出这些士兵的个数就行了。 \(S\)向每一行连...

网络流 Luogu

2020-06-12

0 356