苟且的狮子

题解

2020多校(6) CF(27) 作业(3) 区域赛真题题解(提升思维！！！)(8) 寒假模拟赛(1) 未归档(1) 苏州大学排位赛(7) 随笔(1)

/ 注册

全部文章 / 题解（共179篇）

Birthday

最大流，二分题意：分析：这一题，我刚拿到手是蒙B的。我的第一反应也是最小费用最大流，但是想了一会也是不知道该如何表示X^2这个万恶的东西。迫不得已，展开别的思路：我们这样建图：源点S与1~n相连，取cap = 1 无cost1~n与n+1 ~ n+m 按照数据相连 cap = 1,无c...

二分最大流

2020-08-16

1 641

[SDOI2010]星际竞速

建图，网络流，最小费用最大流题意：分析：雨神说过，图论题难就难在建图上。这题我觉得建图还是蛮难的。我们捕捉一下重要信息：从一个额外的点出发，恰好经过每一个点一次，可以进行跳跃，永远是小点连大点。我们不难明白，所谓额外的点其实就是时空跳跃的中介点，也同时是起点。同时，我们也很本能的想将所...

最小费用最大流建图

2020-08-15

2 968

勤奋的杨老师（二）

最大点权闭合子图题意： ##题解：这时一道非常模板的最大点权闭合子图问题。但是，我们不知道最大点权闭合子图是什么。。。。。。现在，有我来告诉你：有一堆有权值的点，权值可以为正为负为零。这些点有一些如图的相对顺序：即，这个图中会有一些树！图可能原本是这样的：图具体长什么样无所谓，你只要知道这些图...

最大点权闭合子图

2020-08-15

2 583

Collect Jewel

最小费用最大流题意：分析：这是我第一次做最小费用最大流的题目。感觉还行，写个题解留作纪念。意识到这是个关于最小费用最大流问题并不难。但是，关键在于如何建图。拆点是一定的。我刚开始想，对每一个节点，拆成两个。原节点到拆点一条c=1 d=-vi 的路拆点到原节点一条c=inf,d=0的路。...

最小费用最大流

2020-08-15

1 576

方格取数(2) HDU - 1569

网络流，最大权独立点集题意： ##分析：看到这一题，我的第一反应是二分图求最大独立点集。想要用HK算法干掉他。但是仔细一看并非如此，题目让球的是最大权独立点集。这就是完全不同的问题了。真正的解法推荐看论文：胡伯涛《最小割模型在信息学竞赛中的应用》，直接跳到第五部分读就行了。不得不感叹，真是巧妙...

网络流最大点权独立集最小割

2020-08-14

1 900

kebab HDU - 2883

网络流，离散化题意：分析：不妨先看看这一题：hdu3572可以先做这题会发现这两题几乎一摸一样不同之处在于：1.本题时间跨度大足足有100W,所以如果按照原先的思路我们是要对其离散化的2.本题中的肉串可以分成k块同时烤制3.本题中一种肉块有n个我们要解决这三点。先从2，3开始：一块肉可以...

网络流离散化

2020-08-14

1 496

[JSOI2010]GROUP 部落划分 GROUP

kruskai，贪心题意：分析：这一题我是由kruskai算法为突破口的。我们想想，对于一揽子的节点，我们要对他们进行并查集操作，将其合成k个集合。然后求集合间的最短距离。我们想让这个最短距离尽量大！由kruskai算法作为突破口，我们不妨对所有的边按照其权值从小到大排序。边：共有n*...

kruskai 贪心

2020-08-09

4 659

白金元首与独舞

矩阵树这题不错，又学到了一个知识点。欸嘿嘿。题意：分析：我们来看这道题：首先，我们不妨把外面虚拟成一个点。那么问的就是，矩形中的所有点能否到达外面的点。这时，我们想想。如果能都联通的话应该会是什么情况？首先肯定有一些点本来就联通。我们以虚构的最外面的点出发，进行深度优先搜索。肯定能将...

dfs 矩阵树

2020-08-09

2 562

Graph Coloring I

dfs 题意：分析：深搜没学好啊！我们会发现，这其实就是一个判断图是否是二分图的过程！那么，我们已知，二分图是没有奇数环的。所以，我们可以断定，要不可以染色，要不有奇数环！染色部分容易，广搜深搜都可以，分深度奇偶染色即可。但是，要我们找环，就有点困难了。因为要是环，所以我们选择深搜，因为要...

dfs 二分图

2020-08-02

2 681

白色相簿

并查集题意：分析：很简单，直接并查集。自己再改改，维护一个cnt[i]记录集合i中有多少个元素就可以了。题解并不是我真正的目的，我真正的目的是：我永远喜欢小木曾雪菜！！！！！！！！！代码如下： #include<iostream> #include<algorith...

并查集

2020-08-02

2 717