博文
并查集的应用PKU1703(2008-08-21 13:13:00)
摘要：///////////////////////////////////////////作品名称:并查集应用//作者姓名:满天飞//作品时间:2008-8-15//最后修改:2008-8-15//Q Q 号码:280282813//版权所有,翻版必究/////////////////////////////////////////#include<stdio.h>#define MAX 100010int ary[MAX];int opt[MAX];void Init(int n){ int i; for(i = 0; i <= n+10; ++i) { ary[i] = -1; opt[i] = -1; }}int Find(int index){ if(ary[index] < 0) return index; return ary[index] = Find(ary[index]);}int Union(int first, int second){ int i, j; if(second == -1) return first; i = Find(first); j = Find(second); if(i == j) return i; if(ary[i] < ary[j]) { &......
并查集的应用PKU2524(2008-08-21 13:12:00)
摘要：///////////////////////////////////////////作品名称:并查集应用//作者姓名:满天飞//作品时间:2008-8-15//最后修改:2008-8-15//Q Q 号码:280282813//版权所有,翻版必究/////////////////////////////////////////#include<iostream>using namespace std;class Set{ private: int* ary; int length; public: int Find(int index); bool Union(int first, int second); Set(int n); int Count(); virtual ~Set(){delete[]ary;}};int Set::Count(){ int i, ct; ct = 0; for(i = 1; i <= length; ++i) { if(ary[i] < 0) ct++; } return ct;}Set::Set(int n){ &nbs......
并查集的应用PKU2492(2008-08-21 13:11:00)
摘要：///////////////////////////////////////////作品名称:并查集应用//作者姓名:梁岳传//作品时间:2008-8-15//最后修改:2008-8-15//Q Q 号码:280282813//版权所有,翻版必究/////////////////////////////////////////#include<iostream>using namespace std;#define MAX 1000010int ary[MAX];int opt[MAX];void Init(int n){ int i; for(i = 0; i <= n+10; ++i) { ary[i] = -1; opt[i] = -1; }}int Find(int index){ if(ary[index] < 0) return index; return ary[index] = Find(ary[index]);}int Union(int first, int second){ int i, j; if(second == -1) return first; i = Find(first); j = Find(second); if(i == j) return i; if(ary[i] < ary[j]) ......
并查集的应用PKU2236(2008-08-21 13:10:00)
摘要：///////////////////////////////////////////作品名称:并查集应用//作者姓名:梁岳传//作品时间:2008-8-16//最后修改:2008-8-16//Q Q 号码:280282813//版权所有,翻版必究////////////////////////////////////////#include<iostream>#include<cmath>using namespace std;typedef struct{ int x; int y; int parent;}Node;class Set{ public: Node* ary; int length; public: int Find(int index); bool Union(int first, int second); Set(int n); virtual ~Set(){delete[]ary;}};Set::Set(int n){ int i; ary = new Node[n+10]; length = n; for(i = 1; i <= n; ++i) { cin>>ary[i].x>>ary[i].y; &......
线段树的应用PKU2985(2008-08-21 13:00:00)
摘要：///////////////////////////////////////////作品名称:并查集及线段树应用//作者姓名:满天飞//作品时间:2008-8-18//最后修改:2008-8-18//Q Q 号码:280282813//版权所有,翻版必究//////////////////////////////////////////写得要死终于过了#include<iostream>using namespace std;typedef struct{ int lbound; //左界 int rbound; //右界 int left; //左子树 int right; //右子树 int ct; //覆盖次数}TreeNode;class SegmentTree{ private: int nodenum; TreeNode* tree; public: SegmentTree(int); virtual ~SegmentTree(){delete[]tree;} //构建树 void build(int, int); //插入一个数 void insert(int); //删除一个数 void erase(int); ......
线段树的应用PKU3264(2008-08-21 12:31:00)
摘要：#include <iostream>using namespace std;typedef struct{ int lbound, rbound; int left, right; int minnum, maxnum;}TreeNode;class SegmentTree{ public: int nodenum; TreeNode* tree; public: SegmentTree ( int ); void build ( int, int ); void insert ( int, int ); void search ( int, int, int); virtual ~SegmentTree() {delete[]tree;}};//当区间长度小于128时采用顺序查找,以减少递归带来的开销const int len = 128;//存储区间权重int ary[50010];//最大最小值int Max;int Min;SegmentTree::SegmentTree ( int a ){ tree = new TreeNode[2*a+10]; memset ( tree, 0, sizeof ( TreeNode ) * ( 2*a+10 ) ); nodenum = 0; build ( 1, a );}vo......
并查集的实现及应用:最小生成树(2008-08-15 10:40:00)
摘要：///////////////////////////////////////// //作品名称:并查集的实现及应用
//作者姓名:梁岳传//作品时间:2008-8-15//最后修改:2008-8-15 //Q Q 号码:280282813 //版权所有,翻版必究 ///////////////////////////////////////// #include<iostream>
using namespace std;
class Set{private: int* ary; int length;public: int Find(int index); bool Union(int first, int second); Set(int n); virtual ~Set(){delete[]ary;}
};
Set::Set(int n){ int i; ary = new int[n]; length = n; for(i = 0; i < n; ++i) ary[i] = -1;}
//将每次查找过的路线上的结点全部都指向根结点int Set::Find(int index){ int i, j, t;
if(index < 0 || index >= length) return -1; //查找index元素的根结点 for(i = index; ary[i] >= 0; i = ary[i]); //将这条路线上的所有元素全部指向根结点 for(j = index; j != i; j = t){ t = ary[j]; ary[j] = i; }
return i;}
//树的根结点保存树的元素个数,以负值的形式保存bool Set::Union(int first, int second){ int i, j; if(first < 0 || first >= length) re......