首页 > 其他 > 详细

LR杂记 - loadrunner结果各种指标分析

时间:2014-05-20 15:54:34      阅读:385      评论:0      收藏:0      [点我收藏+]

题目:

    链接:点击打开链接

题意:

    有n个朋友,编号为1......n。知道其中一些人相互认识,求最少需要多少桌子。

算法:

    并查集算法的模板题。

    (来源:LCY-teacher课件)

    >>在某个城市里住着n个人,现在给定关于 n个人的m条信息(即某2个人认识)假设所有认识的人一定属于同一个单位,请计算该城市最多有多少单位?

  >>如何实现?

  >>什么是并查集?

  >>英文:Disjoint Set,即“不相交集合”将编号分别为1…N的N个对象划分为不相交集合,在每个集合中,选择其中某个元素代表所在集合。常见两种操作:I.两个集合.II.找某元素属于哪个集合

  >>实现方法1:用编号最小的元素标记所在集合;定义一个数组set[1..n] ,其中set[i] 表示元素i 所在的集合。

find1(x)
{
    return set[x];
}

Merge1(a,b)
{    i = min(a,b);
     j = max(a,b);
     for (k=1; k<=N; k++) {
         if (set[k] == j)
            set[k] = i;
     }
}

对于合并我们必须搜索全部元素,效率太低。

    >>考虑用树结构?

    >>

n每个集合用一棵“有根树”表示
n定义数组 set[1..n]
nset[i] = i , 则i表示本集合,并是集合对应树的根
nset[i] = j, j<>i, 则 j 是 i 的父节点. 
    >>代码:
merge2(a, b)
{
    if (a<b)
       set[b] = a;
    else
       set[a] = b;
}

find2(x)
{
   r = x;
   while (set[r] != r)
      r = set[r];
   return r;
}

最坏情况Θ(N)

    >>避免最坏情况:

n方法:将深度小的树合并到深度大的树
n实现:假设两棵树的深度分别为h1和h2, 则合并后的树的高度h是:
nmax(h1,h2), if h1<>h2.
nh1+1, if h1=h2.
n效果:任意顺序的合并操作以后,包含k个节点的树的最大高度不超过
merge3(a,b)
{ if (height(a) == height(b)) {
       height(a) = height(a) + 1;
       set[b] = a; 
   } else if (height(a) < height(b))
      set[a] = b;
   else  
      set[b] = a; 
 }
find2(x)    
{
   r = x;
   while (set[r] != r)
      r = set[r];
   return r;
}

路径压缩:
n思想:每次查找的时候,如果路径较长,则修改信息,以便下次查找的时候速度更快
n步骤:
n第一步,找到根结点
n第二步,修改查找路径上的所有节点,将它们都指向根结点
find3(x)
{
      r = x;
      while (set[r] <> r) //循环结束,则找到根节点
          r = set[r];       
      i = x;
      while (i <> r) //本循环修改查找路径中所有节点
      {   
          j = set[i];
         set[i] = r;
          i = j;
      }
}



思路:

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int n,m,a,b,cnt;
int father[1010];

int getfather(int n)
{
    while(n != father[n])
        n = father[n];
    return n;
}

void Union(int x,int y)
{
    int rootx = getfather(x);
    int rooty = getfather(y);
    if(rootx != rooty)
        father[rooty] = rootx;
}

int main()
{
    //freopen("input.txt","r",stdin);
    int t;
    cin>>t;
    while(t--)
    {
        getchar();
        cnt = 0;
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
            father[i] = i;
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d",&a,&b);
            Union(a,b);
        }
        for(int i=1; i<=n; i++)
        {
            if(father[i] == i)
                cnt++;
        }
        printf("%d\n",cnt);
    }
    return 0;
}


LR杂记 - loadrunner结果各种指标分析,布布扣,bubuko.com

LR杂记 - loadrunner结果各种指标分析

原文:http://blog.csdn.net/a578133380/article/details/26171643

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!