最近老师布置个作业,很没有头绪,于是各种咨询,大家的解决方案是使用最小费用最大流模型来求解,于是我便花了 3 天时间来理解这个算法.

问题描述 ​

问题很简单,你有一个只有 5 个房间的酒店,然后本周会有 18 个订单到来,怎样接受订单可以使本周的收益达到最大值.也就是把这 18 个订单填写到一个 5*7 的表格里 怎么填收益最大,订单要么接受要么拒绝,也可以说是典型的 01 背包问题吧,但用动态规划不好抽象出来状态转移方程,所以我还是选择用最大流来做.每个订单包含 3 个信息:每晚付的房费,从周几开始入住,入住几天.

抽象数据模型 ​

因为题目要求是球最大收益,而流模型是最小费用,所以我们把收益取相反数即可.关键是建立容量和权值,因为房间的数量是 5,所以限制源点和汇点的容量是 5,权值是 0.然后中间设置 8 个点,产生 7 条边,每条边代表每天的流,权值为 0,容量为无穷大.这里我们不能简单的连接点来设置订单的边,因为有相同的起始日期和结束日期的订单.这样会造成冲突,如何解决冲突呢? 我们可以在订单的边上再加一个顶点来进行区分.模型图如下所示: 顶点 11 和顶点 16 是重复边的订单,对应的是第一个订单和第 6 个订单.源码和输入数据可以在文章末尾看到.

查找增广路径 ​

这里我们使用Ford–Fulkerson算法来计算每次的增广路径.

路径的查找 ​

每次增广路径的查找都需要得到最小权值的路径.查找路径使用的是SPFA算法.

第一次查找增广路径 ​

第二次查找增广路径 ​

以此类推求出最后的结果~

参考: ​

Source code

Ford–Fulkerson

V 社的 steam 平台在 Linux 下出了这么多年还是没解决输入法的问题.本身官方也就只支持 Ubuntu,所以在其它发行版也就难免会有各种各样的问题.容我慢慢道来

Alt 键无法发信号 ​

Dota2 只能通过 Alt 和鼠标左键的配合发信号.无法像 Dota 一样可以单纯使用鼠标发信号.但是有些用户可能发现自己无法发信号. 原因在于你使用的窗口管理器已经为 Alt 和鼠标左键绑定了事件,所以你得取消窗口管理器的事件绑定,例如 openbox 需要修改配置文件 rc.xml 找到鼠标事件并注释掉事件绑定的内容.

双显卡启动游戏 ​

对于很多双显卡的机器,平时运行使用集显但是在玩游戏的时候肯定要使用独显才能充分享受游戏的乐趣.所以启动游戏的时候就必须设置启动参数才行. 启动参数设置为vblank_mode=0 primusrun %command% 前提是你要装上 primusrun.

Dota2 没声音 ​

如果你只使用的 ALSA 没使用 PulseAudio 可能会遇到这个问题,原因是因为 Steam 自己的库文件和系统的冲突.只要把 Steam 的相关 ALSA 库删掉即可. 删掉下面的文件夹 和 libasound.so.*即可搞定.

~/.steam/steam/ubuntu12_32/steam-runtime/i386/usr/lib/i386-linux-gnu/
~/.steam/steam/ubuntu12_32/steam-runtime/amd64/usr/lib/x86_64-linux-gnu/

参考: ​

Steam

Dota 2

实验室给配备了一台高性能的台式机,但是 UEFI 本身关不掉.而且有些操作还是离不开 Windows,于是便折腾 Win10 和 Archlinux 的双启动. 安装双系统基本上都是先装 Windows 再装 Linux 的.切忌这一点,安装顺序反了会很麻烦.

Win10 配置 ​

要安装 Archlinux,首先得对 Windows 进行相应的配置才行.Windows 的安装就不用我介绍了,大家基本都会的.

UEFI Secure Boot ​

首先要进入 BIOS 把这个参数关掉,如果 BIOS 里面有快速启动之类的也关掉.

Fast Start-Up ​

把 Win10 的这个加速系统开机的配置禁用掉,应该在电源管理界面可以禁用的.因为切换系统的话这个功能会导致你丢失数据.

制作 Arch 的 U 盘安装盘 ​

如果你简单的使用dd命令就可以成功安装那是最好不过的了,但是有时候事与愿违...

假设你用 dd 刻录好之后,然后用电脑 U 盘启动,出现启动菜单 选择 Arch Linux archiso x86_64 UEFI CD 之后遇到黑屏的问题.

你可以先试试禁用 KMS

如果这个不行的话,那说明你得采用第二个办法了,使用 GRUB 进行引导启动盘.

手动制作启动盘 ​

因为要使用 GRUB 进行引导,所以不能使用 dd 刻录,dd 刻录的 U 盘有写保护,我们无法修改.我们得手动制作安装盘

# mkdir -p /mnt/{iso,usb}
# mount -o loop archlinux-2015.10.01-dual.iso /mnt/iso
# mount /dev/sdXn /mnt/usb
# cp -a /mnt/iso/* /mnt/usb
# sync
# umount /mnt/iso

光是拷贝还不行,我们还得有引导信息. 使用 syslinux 进行引导

# cp -r /usr/lib/syslinux/bios/*.c32 /mnt/usb/arch/boot/syslinux/  ## copy ALL the *.c32 files from /usr/lib/syslinux/bios/, DO NOT SYMLINK
# extlinux --install /mnt/usb/arch/boot/syslinux/

如果你的 U 盘是 MBR 格式的,记得使用 fdisk 把当前分区设置为活动分区. fdisk /dev/sdX 然后输入 a 命令,选择要设置的活动分区.

还有 U 盘寻找启动分区是根据 U 盘的 label 标签来寻找的,确保你的卷标是 ARCH_2015XX 格式. 如果你不想用卷标的话,还可以用 UUID. 查找你 U 盘的 UUID 的命令是 sudo blkid.

制作 GRUB standalone ​

这才只是手动制作好了启动 U 盘.你还要切换成 GRUB 引导.通过下面的命令制作出一个带有所有模块的 GRUB 引导文件.

grub-mkstandalone -d /usr/lib/grub/x86_64-efi/ -O x86_64-efi --modules="part_gpt part_msdos" --fonts="unicode" --locales="en@quot" --themes="" -o "/tmp/grubx64_standalone.efi"

生成的 grubx64_standalone.efi 就是我们需要的文件.

然后回到我们的那个启动 U 盘.备份 EFI/boot/loader.efi 成 EFI/boot/gummiboot.efi.

拷贝两份 grubx64_standalone.efi. 分别命名为 EFI/boot/loader.efi 和 EFI/boot/bootx64.efi.

然后新建一个 EFI/boot/grub.cfg 把 wiki上的内容拷贝过去.记得替换掉 ARCH_YYYYMM 的值.

然后这样就应该用 grub 启动了. 如果你这样还是启动失败了, 得到了类似 invalid magic number的错误.那只能说你跟我一样倒霉.

用 GRUB 挂载 ISO 进行引导 ​

既然我们的 GRUB 是好的,那我们就用 GRUB 直接引导一个完整的 ISO 文件. 参考我之前发布的文章使用 GRUB2 引导 ISO 镜像.

在原有的 grub.cfg 上添加一个 menuentry.并把完整的 ISO 镜像拷贝到 U 盘里面.记得替换 UUID 和文件名.

menuentry "Archlinux-x86_64.iso" --class iso {
  set isofile="/archlinux-2013.04.01-dual.iso"
  search -s -f -n /archlinux-2013.04.01-dual.iso
  probe --set=DB7B-2C3D -u $root
  loopback loop /archlinux-2013.04.01-dual.iso
  linux (loop)/arch/boot/x86_64/vmlinuz archisolabel=ARCH_201304 img_dev=/dev/disk/by-uuid/DB7B-2C3D  img_loop=$isofile earlymodules=loop
  initrd (loop)/arch/boot/x86_64/archiso.img
}

这次总算可以引导出 arch 的安装环境了.接下来就是按照正常的步骤进行安装了. 在 Win 下直接使用Rufus刻录就没那么折腾了.

安装 Archlinux 之后配置双系统的 GRUB ​

到最后我们要安装 GRUB 到 UEFI上.如果你提前安装过 Windows,那么你肯定有 EFI 分区的.

# pacman -S dosfstools grub efibootmgr
# mkdir /boot/efi
# mount /dev/sda1 /boot/efi

把 EFI 分区挂载到系统上,然后安装 GRUB.

# grub-install --target=x86_64-efi --efi-directory=/boot/efi --bootloader-id=grub --recheck
# grub-mkconfig -o /boot/grub/grub.cfg

生成的 grub.cfg 里面并没有 Windows 的启动菜单,我们需要手动写.

menuentry "Microsoft Windows 10" {
    insmod part_gpt
    insmod fat
    insmod search_fs_uuid
    insmod chain
    search --fs-uuid --set=root $hints_string $fs_uuid
    chainloader /EFI/Microsoft/Boot/bootmgfw.efi
}

$hints_string 的值是命令# grub-probe --target=hints_string /boot/efi/EFI/Microsoft/Boot/bootmgfw.efi的输出.

$fs_uuid 的值是命令# grub-probe --target=fs_uuid /boot/efi/EFI/Microsoft/Boot/bootmgfw.efi的输出.

替换这俩值,保存并退出即可.到此双系统配置完毕.最后别忘了进 BIOS 把第一启动项目设置为 GRUB.

参考 ​

Preinstalled Windows 8.1 and Arch Linux dual boot

Unified Extensible Firmware Interface

USB flash installation media

Syslinux

GRUB