poj1456

这题并查集的用法非常巧妙。
思路:首先是贪心思想:按profit从大到小对这些产品进行排序,然后从pro[1]开始卖产品,对于产品pro[i],在距它的deadline最近的空的那天卖出,如果这一天是0,说明从pro[i].d到1这些天都已经被占用(一天只能卖出一件product),即这件产品无法被卖出。
用并查集优化:先算出最大的day,然后从0到day,每天都是并查集的一个元素。当连续的几天被占用的时候,把它们并入一个集合,根是这些被占用的连续的几天左边最近的未被占用的那天。如果根为0,说明这个product无法卖出。
但是这样贪心的正确性我还没有证明,求大神告知。

hdoj1325

盯着网络流题看了半天还是不会做,好吧,还是做下并查集。
思路:首先把边当成无向边,保证无环,有环必不为树(并查集)。其次,保证只有一个点的入度为0,其他点的入度为1(设置数组)。最后还要满足连通(遍历并查集)。
注意两个地方:1.点的编号不一定连续。2.可能出现空树的case。

带权值的并查集

/*
根据不同题目的要求,merge()可以单独写,也可以并在main()中。
d[i]可以表示i与其父结点间的距离,当执行find(i)后,i的父亲会变成根(路径压缩),所以d[i]就变成了i到根的距离(当然其实也可以认为d[i]的意义没变,仍为i到其父节点的距离,因为路径压缩后,i的父节点就是根结点)
当然,这个域在具体题目中可以有更丰富的含义
注意:在合并时要保持两个集合的根的d[]属性正确。
*/
#include<stdio.h>
#include<stdlib.h>
int find(int x)
{
	if(bin[x]!=x)
	{
		int root=find(bin(x));
		d[x]+=d[bin[x]];
		return bin[x]=root;
	}
	else
		return x;
}

int main()
{

system("pause");
return 0;
}

hdoj1116

开始思路想错了,想的太简单。无奈,,还是看了解题报告。。弱爆了,,发现原来是欧拉道路。。仔细想想,,原来这么简单。回头看看自己的程序,发现其实就是做了判欧拉道路的工作。于是加入并查集判连通的部分。

并查集样例

用并查集可以对无向图判环,每读入一条边,合并该边的两个顶点所在的集合,如果合并时两个顶点已经在一个集合中(说明已经有一条路径连通这两个顶点),则说明出现了环。
用并查集可以对有向图和无向图判连通性。