首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >食物链POJ1182总结

食物链POJ1182总结

作者头像
kalifa_lau
发布2018-04-28 14:46:35
7370
发布2018-04-28 14:46:35
举报
文章被收录于专栏:kalifaの日々kalifaの日々

这道题是用并查集来解。并查集可以高效的查找某个元素是否属于一个集合。 敲代码过程中一次遇到了如下问题:

new 的使用问题

想开辟一块放100个整形变量的空间,我这样写的:

 int *father = new  int(100);

给这个int数组赋值的时候一直报错,觉得自己一定是开辟空间的时候搞错了。 果然,new A(100)的写法是说,把变量的值初始化成100。 想要开辟100个A类型的变量空间,应该这么写:

int *father=new int[100];

按照《挑战程序设计竞赛》思路写出的代码超时

我在看这边书的时候就一直有一个疑问,作者是不是由于原先写惯了C语言,C++里面的cin和cout用着不顺手,所以还特别费事儿的加上#include<cstdio>的头文件,并且输入输出用printf和scanf。 今天我按照这本书的思路写了1182这一题,发现一直超时,把cin改成scanf就AC了,百度了一下发现很多文章讨论它俩性能的差异。得出的结论是,程序设计题尽量用scanf而不是cin。

源代码

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

class union_find
{
private:
        int* father;
        int* height;
        int n;
public:
    union_find(int n)
    {

        this->n = n;

        father = new int[n];

        height = new int[n];
        for(int i=0;i<n;i++)
        {

            father[i]=i;
            height[i]=0;
        }

    }
    ~union_find()
    {
        delete []father;
        delete []height;
    }
    int _find(int x)
    {
        if(x>=n)
        {

            return 0;
        }
        if(father[x]==x)
        {
            return x;
        }
        else
        {
            return father[x]=(_find(father[x]));
        }
    }
    void unite(int x,int y)
    {
        if(x>=n||y>=n)
        {

            return;
        }
        x = _find(x);
        y = _find(y);
        if(height[x]<height[y])
        {
            father[x]=y;
        }
        else
        {
            father[y]=x;
            if(height[x]==height[y])
            {
                height[x]++;
            }
        }
    }

    bool same(int x,int y)
    {
        return _find(x) == _find(y);
    }

};



int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
   // cin>>n>>k;


    union_find f(n*3);

    int ans=0;

    for(int i=0;i<k;i++)
    {
        int t,x,y;
        //cin>>t>>x>>y;
        scanf("%d%d%d",&t,&x,&y);

        x = x-1;
        y = y-1;

        if(x<0||x>=n||y<0||y>=n)
        {

            ans++;
            continue;
        }
        if(t==1)
        {
            if(f.same(x,y+n)||f.same(x,y+2*n))
            {

                ans++;
                continue;
            }
            else
            {
                f.unite(x,y);
                f.unite(x+n,y+n);
                f.unite(x+2*n,y+2*n);
            }
        }
        else
        {
            if(f.same(x,y)||f.same(y,x+n))
            {
                ans++;
                continue;
            }
            else
            {
                f.unite(x,y+n);
                f.unite(x+n,y+2*n);
                f.unite(x+2*n,y);
            }
        }
    }
    cout<<ans<<endl;
    return ans;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017.12.07 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • new 的使用问题
  • 按照《挑战程序设计竞赛》思路写出的代码超时
  • 源代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档