博文
并查集的应用PKU1703(2008-08-21 13:13:00)
摘要：/////////////////////////////////////////
//作品名称:并查集应用
//作者姓名:满天飞
//作品时间:2008-8-15
//最后修改:2008-8-15
//Q Q 号码:280282813
//版权所有,翻版必究
/////////////////////////////////////////
#include<stdio.h>
#define MAX 100010
int 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);
并查集的应用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)
......
并查集的应用PKU2492(2008-08-21 13:11:00)
摘要：/////////////////////////////////////////
//作品名称:并查集应用
//作者姓名:梁岳传
//作品时间:2008-8-15
//最后修改:2008-8-15
//Q Q 号码:280282813
//版权所有,翻版必究
/////////////////////////////////////////
#include<iostream>
using namespace std;
#define MAX 1000010
int 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 ......
并查集的应用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;
......
线段树的应用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);
//插入一个数
&n......
线段树的应用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];
......
并查集的实现及应用:最小生成树(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;