UnionFind

问题描述

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：

• $Find$：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
• $Union$：将两个子集合并成同一个集合。

由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法，MakeSet，用于建立单元素集合。有了这些方法，许多经典的划分问题可以被解决。
为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着，$Find(x)$返回 x 所属集合的代表，而$Union$使用两个集合的代表作为参数。

更进一步的，当两个元素之间的关系可以量化，并且关系可以合并时，可以使用带权并查集来维护元素之间的关系。

带权并查集即是结点存有权值信息的并查集。

System of Difference Constraints

问题描述

首先先引入一个通用的线性规划问题，给定一个$m \times n$的矩阵A，一个$m$维的向量$b$和一个$n$维向量$c$。希望能够找到一个$n$维的向量$x$，使得在由$Ax \leqslant b$给定的$m$个约束条件下优化目标函数$\sum_{i = 1}^n c_ix_i$，使得目标函数的取值最大。有时，我们并不关心目标函数，而是仅仅希望能找到一个可行解，即找到任何满足$Ax \leqslant b$的向量$x$，或者判断不存在可行解。

观察一个特例情况，如果线性规划的矩阵$A$的每一行包括一个1和一个-1，其他的所有项皆为0。则对于$Ax \leqslant b$所给出的约束条件变为$m$个涉及$n$个变量的差额限制条件，此时每个约束条件退化为简单的线性不等式：$x_j - x_i \leqslant b_k$。这里$1 \leqslant i, j \leqslant n$，$i \neq j$，且$1 \leqslant k \leqslant m$。

ASPLOS半日行

真是出乎意料，自己能以本科生的身份

体验了计算机顶级会议ASPLOS 2017

作为一个还在刷 CSAPP 的小白，十分幸运能够来到西安，和众多世界级的科学家坐在一起，聆听并感受CS最前沿的科技革新。在此，首先要感谢的是为我们争取机会的@石老师，以及同行的15级ACM班全体大佬们。

2016 Summary

一学期竟然过的这么快，真是难以想象。暮然回首时，仿佛还能看见昔日的我。

致往日的我

“ flag 就是用来被推翻的。”

报名时的我

依稀记得大一军训的时候，听到了联创这个团队。

Hello World

Stay Single, Stay Simple

1
2
3
4
5

#include<stdio.h>
int main (int argc, char *argv[])
{
  printf("Hello, World!\n");
}

极客到极致

欢迎访问我的Github

小小Q

基于Objective-C纯代码的实时聊天应用，使用图灵机器人API接口并支持图片搜索等多种模式的对话沟通。支持本地推送 3D-Touch等等功能。

简介

我的第一个成型的APP，开发的第一步。