跳至内容

URoQa's Blog

  • 首页
  • 文章分类
    • 动态规划
      • 动态规划->概率&期望DP
    • 图论
      • 图论->最短路
      • 图论->欧拉回路
    • 数据结构
      • 数据结构->并查集
      • 数据结构->单调队列
      • 数据结构->树状数组
      • 数据结构->线段树
    • 数学
      • 数学->容斥原理
      • 数学->概率&期望
      • 数学->莫比乌斯反演
    • 基本算法
      • 基本算法->模拟
      • 基本算法->贪心
      • 基本算法->前缀和
      • 基本算法->二分法
      • 基本算法->差分
      • 基本算法->归并排序
  • 文章列表
  • 关于

【模板】线段树模板(2018-1-31更新)

线段树模板,经过重新整理。
我发现我不会写线段树了,于是重新学了一遍。
我怎么这么菜啊。。。
传送门

阅读更多

2018年1月31日URoQa数据结构->线段树

【模板】最小费用流模板

(待更新)

阅读更多

2018年1月17日URoQa网络流、网络流->费用流

【题解】搭配飞行员 网络流24题 二分图最大匹配

Prelude

传送到LOJ
这是一道二分图最大匹配的裸题,直接水过去就好。。。

阅读更多

2018年1月17日URoQa网络流、网络流->最大流网络流24题

【题解】太空飞行计划 网络流24题 最小割 最大闭合权子图

(待更新)

Prelude

传送到LOJ
虽然是网络流24题中的T2,但是挺难的,至少我之前不知道什么是最大闭合权子图。

阅读更多

2018年1月17日URoQa网络流、网络流->最大流网络流24题

【题解】魔术球 网络流24题

Prelude

传送到LOJ
又一道不会做的题。。。
这题其实就是最小路径覆盖。

阅读更多

2018年1月17日URoQa网络流、网络流->最大流网络流24题

【题解】最小路径覆盖 网络流24题

传送到洛谷
传送到LOJ

Solution

这题也用到了拆点的方法,将原图中的每个点拆成入点和出点,并增加\(S\)点和\(T\)点。然后按原图连有向边,容量为1,再从\(S\)到所有入点、所有出点到\(T\)分别连容量为1的有向边。最少路径数等于\(n\)减去网络最大流。

阅读更多

2018年1月17日URoQa网络流、网络流->最大流网络流24题

【题解】圆桌聚餐 网络流24题

额。。。其实挺简单的。。。只是我比较辣鸡,交了好几次才对。

阅读更多

2018年1月16日URoQa网络流、网络流->最大流网络流24题

【题解】星际转移问题 网络流24题

Prelude

传送到洛谷:→_→
传送到LOJ:←_←
这道题看着觉得特别复杂,不太会做,加上刚学网络流,对这些题没有什么思路。就这样,看了看WC2017讲义上的题解,大概知道思路了,后来还是不太会,又看了看别人的代码。。。

阅读更多

2018年1月2日URoQa网络流、网络流->最大流

一道水题 LOJ6165 线性筛(含线性筛学习笔记)

传送门:https://loj.ac/problem/6165
这题“一道水题”,一道非常难的数学题。(主要是我不会线性筛)

阅读更多

2017年12月31日URoQa数学、数学->数论、数学->数论->线性筛素数LOJ

【模板】最大流Dinic算法模板

传送门:https://www.luogu.org/problemnew/show/3376
先跑BFS判断和建层次图,再跑DFS即可。理论时间复杂度\(O(n^2\times m)\),实际上会更优。

阅读更多

2017年12月28日URoQa网络流、网络流->最大流
  • 1
  • 2
  • 3
  • »

近期文章

  • 【模板】线段树模板(2018-1-31更新)
  • 【模板】最小费用流模板
  • 【题解】搭配飞行员 网络流24题 二分图最大匹配
  • 【题解】太空飞行计划 网络流24题 最小割 最大闭合权子图
  • 【题解】魔术球 网络流24题

近期评论

    文章归档

    • 2018年1月
    • 2017年12月
    • 2017年11月
    • 2017年10月
    • 2017年8月

    分类目录

    • 动态规划
    • 动态规划->斜率优化
    • 图论
    • 图论->最短路
    • 基本算法
    • 基本算法->二分法
    • 基本算法->前缀和
    • 基本算法->差分
    • 基本算法->归并排序
    • 所有文章
    • 数学
    • 数学->数论
    • 数学->数论->线性筛素数
    • 数据结构
    • 数据结构->堆
    • 数据结构->并查集
    • 数据结构->树状数组
    • 数据结构->线段树
    • 网络流
    • 网络流->最大流
    • 网络流->费用流

    功能

    • 登录
    • 文章RSS
    • 评论RSS
    • WordPress.org
    赣ICP备19011074号-1
    Copyright © 2017 - 2021 URoQa All Rights Reserved!