Andrewei's Blog
0%

发表于 更新于 分类于

最近有在Ubuntu系统上连接L2TP/IPsec协议的VPN的需求，所以在网上搜了一波，发现一名叫做Werner Jaeger的大神开发了一款名叫 l2tp-ipsec-vpn 的软件可以解决这个问题。但是在 Ubuntu16.04LTS 系统上，这个款软件的软件源已经不存在，后来在 Enabling L2TP over IPSec on Ubuntu 16.04 这里看到了解决方法，为了做个备份写下这篇博客。

阅读全文 »

发表于 更新于 分类于 ，

预备知识

  1. 树的遍历
  2. 二叉树的基本知识
  3. 排序二叉树的基本知识
  4. 线段树区间更新和区间查询知识
  5. 平衡排序二叉树的基本知识(非必须)

简介

伸展树(SplayTree) 是一种经过改进的平衡排序二叉树, 他跟平衡二叉树的操作非常类似，同时也有很多不同。

阅读全文 »

发表于 更新于 分类于 ，

引入

早就听说过这个数据结构，但是他所做的事情线段树都可以做。年少无知的我以为知道了线段树就可以不去理会这个数据结构，然而每次做题，都要敲长长的线段树，心里苦啊。 不就是一个树状数组么，去看！

阅读全文 »

发表于 更新于 分类于 ，

ubuntu 安装 deb 软件包的方法有两种

  1. 直接双击 deb 文件, 此时会自动调用系统的软件中心然后根据提示进行安装
  2. 作为程序员当然要用一种逼格高的方法来解决这个问题——用命令行来安装。ubuntu 下可以使用 dpkg 命令来安装, 下面是 dpkg 常用的几个命令:
    阅读全文 »

发表于 更新于 分类于 ，

题目链接：http://poj.org/problem?id=1273

题目大意:

下雨的时候约翰的田里总是积水，积水把他种的三叶草给淹了，他于是做了若干排水沟，每条沟在起始处安置一个阀门来控制这条沟的最大排水量，现在给出沟的条数以及阀门的个数。并给出每条沟的最大排水量。约翰的田里的积水处是阀门1，排出水的位置是最后一个阀门。求约翰在处理积水时的最大排出量。

阅读全文 »

发表于 更新于 分类于 ，

基本概念(从书上摘抄,可以直接跳过不看)

容量网络和网络最大流

** 容量网络: ** 设 G(V, E)是一个有向网络, 在 V 中指定了一个顶点, 称为源点(记为 Vs ), 以及另一个顶点, 称为汇点(记为 Vt); 对于每一条弧 <u, v>∈E, 对应有一个权值 c(u, v)>0, 称为弧的容量, 通常把这样的有向网络 G 称为容量网络。

也就是指: 一个拥有源点、汇点并且可以容纳流量的图.

** 弧的流量: ** 通过容量网络 G 中每条弧 <u, v> 上的实际流量(简称流量), 记为 f(u, v)。
** 网络流: ** 所有弧上流量的集合 f = { f(u, v) },称为该容量网络 G 的一个网络流。
** 可行流: ** 在容量网络 G(V, E) 中, 满足以下条件的网络流 f, 称为可行流:

  • ** 弧流量限制条件: ** $ 0 ≤ f(u, v) ≤ c(u, v)$
  • ** 平衡条件: ** 除了 Vs, Vt 外, 其余的点流入的流量总和等于流出的流量总和, 其中 Vs 流出的流量总和 - 流出的流量总和 = f, Vt 流入的流量总和 - 流出的流量总和 = f, 并且称 f 为可性流的流量.

也就是指: 在图中有一条从 Vs 到 Vt 的路径, 这条路径上起点 $f_o - f_i = f$, 终点 $f_i - f_o = f$， 其他的点 $f_i == f_o$, 并且所有的边的当前流量小于等于最大流量.(其中 $f_i$ 代表流入流量, $f_o$ 代表流出流量)

阅读全文 »