loj 6226. 「网络流 24 题」骑士共存问题
1. 题目链接
2. 题目描述
3. 解题思路
题目中要求如果一个顶点被选择,那么8个方向上的顶点就不能被选择。显然,这很像二分图的染色问题。
将每个非障碍的顶点与其8个方向上的非障碍顶点连一条边,那么本题就是一个求最大独立集的问题,而且是一个求二分图的最大独立集的问题。
为什么是二分图呢?可以从下面两条性质来分析:
- 对于任意节点$u$,不可能经过奇数步回到节点$u$,实际上,这就是
匈牙利算法 Hungary
的进行二分图的判断的主要思想; - 按照题目中那个图,将所有顶点划分成红色、黄色两类节点,可以发现同色的节点之间没有边。
而二分图上有很好的性质,比如:
- 最大匹配数 = 最小点覆盖;
- 最大独立集 = 最小边覆盖 = 顶点数 $\lvert V \lvert$ - 最大匹配数;
- DAG 的最小路径覆盖数 = DAG 图中的节点数 - 相应二分图中的最大匹配数。
- DAG 的最小路径覆盖是指找最小数目的互相不相交的有向路径,满足 DAG 的所有顶点都被覆盖。
- DAG 对应的二分图这样构造:对于 DAG 中的一个顶点 $p$,二分图中有两个顶点 $p$ 和 $p’$,对应 DAG 中的一条有向边 $p\to q$,二分图中有 $p\to q’$ 的一条无向边。二分图中 $p$ 属于 $S$ 集合,$p’$ 属于 $T$ 集合.
- ……
求二分图的最大匹配数的方法有 匈牙利算法(复杂度$\mathcal O(VE)$) 和 网络流(代表算法就是Dinic/Hopcroft-carp 算法,复杂度$\mathcal O(\sqrt{V}E)$)。
[hdu 5988. Coding Contest] zkw 最小费用最大流
1. 题目链接
2. 题目描述
有 $N$ 个点,$M$ 条边的有向图 $(N\le 100, M\le 5000)$。任意一个点 $i$ 上有$s_i$ 个人,$b_i$ 份食物$(s_i, b_i\le 200)$。
任意一条边 $i$ 有几个属性 $u_i, v_i, c_i, p_i$ $(c_i\le 100, 0\lt p_i\lt 1)$。$u_i, v_i$ 分别表示有向边的两个顶点编号;$c_i$ 表示这条边的最大容量(最多允许几个人通过);点$u_i$ 中的每个人可以沿着这条有向边移动到点 $v_i$,但是除了第一个经过这条边的人不会破坏这条边,剩下的人都会有 $p_i$ 的概率把这条边破坏。图中只要有一条边被破坏了,就认为图被破坏了。
现在需要保证所有人都能拿到一份食物的情况下,求出图被破坏的最小概率。
数据范围:
3. 解题思路
主要思路:拆边 + 对数函数将积性函数转为和性函数 + zkw 最小费用最大流。
网络数据挖掘课程笔记
Overview
搜索/广告-徐
- 置信度、支持度
- 决策树
- 监督学习评价指标:Accuracy/Precision/Recall/F1
- SVD 分解
- Fold-in 算法
- AdaBoost算法
- BM25
- 语言模型Language Model for IR(LM4IR)、平滑化
- 排序学习:基于有序对
- 排序学习评价方法:MAP、NDCG(Normalized Discounted Cumulative Gain)
- TF-IDF计算公式
- 线性感知器
- SVM
- 硬边距:
- 软边距: 松弛变量$\xi$、参数$C$
图数据挖掘-沈
- 无标度网络:数据分布
- 复杂网络的小世界特性
- 连边关系的结构平衡
- 影响最大化问题
- PageRank
- 图聚类算法:Normalized Cut、模块度优化、InfoMap、非负矩阵分解等
推荐系统-罗
- 矩阵分解的核心思想
- 矩阵分解和U-U CF、I-I CF的区别
- U-U CF 的评分
- 相关度的度量:Pearson Correlation
机器学习基本概念(未完待补)
Git 常见错误
Github 大文件删除之后依旧push不上
Counting objects: 24, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (23/23), done.
Writing objects: 100% (24/24), 201.06 MiB | 1.36 MiB/s, done.
Total 24 (delta 5), reused 0 (delta 0)
remote: Resolving deltas: 100% (5/5), completed with 2 local objects.
remote: warning: File model/news.model is 73.08 MB; this is larger than GitHub’s recommended maximum file size of 50.00 MB
remote: warning: File data/user_click_data.tar.gz is 74.27 MB; this is larger than GitHub’s recommended maximum file size of 50.00 MB
remote: error: GH001: Large files detected. You may want to try Git Large File Storage - https://git-lfs.github.com.
remote: error: Trace: a092a0b034ec52cbdd5c6fda7852c00c
remote: error: See http://git.io/iEPt8g for more information.
remote: error: File src/data-utils/train_original.csv is 155.62 MB; this exceeds GitHub’s file size limit of 100.00 MB
To github.com:XingwXiong/NewsRS.git
! [remote rejected] master -> master (pre-receive hook declined)
error: failed to push some refs to ‘git@github.com:XingwXiong/NewsRS.git’
解决办法:1
2
3$ git filter-branch --index-filter \
'git rm -r --cached --ignore-unmatch src/data-utils/train_original.csv' HEAD
$ git push origin master