[带权并查集][图论模型] HDU3038 POJ1182 POJ2492

蒟蒻第一次接触带权并查集ooorz

附上dalao关于并查集的链接 https://blog.csdn.net/tribleave/article/details/72878239

https://blog.csdn.net/niushuai666/article/details/6981689

刚看到这个区间统计向量性真的惊艳了。。神奇操作

HDU 3038

#include
#include
#include
#include

using namespace std;
const int maxn=2e5+5;

int p[maxn],cnt[maxn];

void init(int k)
{
    for (int i=1; i<=k; i++)
    {
        p[i]=i;
        cnt[i]=0;
    }
}

int find(int x)
{
    if(p[x]==x)
    {
        return p[x];
    }
    else
    {
        int px=p[x];
        p[x]=find(p[x]);
        cnt[x]+=cnt[px];//在find之后更新cnt，为什么不会多加？因为尽头的根cnt为0
        return p[x];
    }
}

int main()
{
    int n,m,ans,l,r,s;
    while(~scanf("%d%d",&n,&m))
    {
        ans=0;
        init(n);
        while(m--)
        {
            scanf("%d%d%d",&l,&r,&s);
            int fl=find(l-1),fr=find(r);
            if(fl==fr)
            {
                if(s!=cnt[r]-cnt[l-1])//注意这里都是l-1。。。
                    ans++;
            }
            else
            {
                p[fr]=fl;
                cnt[fr]=cnt[l-1]-cnt[r]+s;//为什么不加cnt[fl]？因为那个是在find里实现的，cnt只处理相对关系
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

POJ 1182 这个我写挫了。。。用带权应该更好些

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include

using namespace std;
typedef long long LL;
const int maxn=150000+5;
const int MOD=1e9+7;

int n;
int par[maxn],rk[maxn];

void init(int n)
{
    for (int i=1;i<=n;i++)
    {
        par[i]=i;
        rk[i]=0;
    }
    n+=50000;
    for (int i=1+50000;i<=n;i++)
    {
        par[i]=i;
        rk[i]=0;
    }
    n+=50000;
    for (int i=1+100000;i<=n;i++)
    {
        par[i]=i;
        rk[i]=0;
    }
}

int find(int x){return x==par[x]?x:par[x]=find(par[x]);}

void unite(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x==y)return ;
    if(rk[x]n||v>n||u<1||v<1)
        {
            cnt++;
            continue;
        }
        if(o==1)
        {
            if(same(u,v+50000)||same(u+50000,v+100000)||same(u+100000,v)||
               same(v,u+50000)||same(v+50000,u+100000)||same(v+100000,v))
            {
                cnt++;
            }
            else
            {
                unite(u,v);
                unite(u+50000,v+50000);
                unite(u+100000,v+100000);
            }
        }
        else
        {
            if(u==v)
            {
                cnt++;continue;
            }
            if(same(u,v)||same(u+50000,v+50000)||same(u+100000,v+100000)
               ||same(v,u+50000)||same(v+50000,v+100000)||same(v+100000,u))//这里有两种冲突，一种是
            {                                                              //u v相同，另一种是v吃u。。
                cnt++;
            }
            else
            {
                unite(u,v+50000);
                unite(u+50000,v+100000);
                unite(u+100000,v);
            }
        }
    }
    printf("%d\n",cnt);
    return 0;
}

POJ 2492 几乎和HDU那个一样，代码都没怎么改。。只不过可耻地加了读入挂刷了个前排

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include

using namespace std;
typedef long long LL;
const int maxn=2e3+5;
const int MOD=1e9+7;


const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar()
{
    if(head==tail)
    {
        int l=fread(buffer,1,BufferSize,stdin);
        tail=(head=buffer)+l;
    }
    return *head++;
}
inline int read()
{
    int x=0,f=1;
    char c=Getchar();
    for (;!isdigit(c);c=Getchar())if(c=='-')f=-1;
    for (;isdigit(c);c=Getchar())x=x*10+c-'0';
    return x*f;
}

int p[maxn],cnt[maxn];

void init(int k)
{
    for (int i=1; i<=k; i++)
    {
        p[i]=i;
        cnt[i]=0;
    }
}

int find(int x)
{
    if(p[x]==x)
    {
        return p[x];
    }
    else
    {
        int px=p[x];
        p[x]=find(p[x]);
        cnt[x]+=cnt[px];
        return p[x];
    }
}

int main()
{
    int n,m,ans,l,r,s,T,ct=0;
    //scanf("%d",&T);
    T=read();
    while(T--)
    {
        ct++;
        //scanf("%d%d",&n,&m);
        n=read();
        m=read();
        ans=0;
        init(n);
        while(m--)
        {
            //scanf("%d%d",&l,&r);
            l=read();
            r=read();
            int fl=find(l),fr=find(r);
            if(fl==fr)
            {
                if(!((cnt[r]-cnt[l])&1))
                {
                    ans=1;
                    while(m--)
                    {
                        //scanf("%d%d",&l,&r);
                        l=read();
                        r=read();
                    }

                    break;
                }

            }
            else
            {
                p[fr]=fl;
                cnt[fr]=cnt[l]-cnt[r]+1;//error?
            }
        }
        printf("Scenario #%d:\n",ct);
        printf(ans?"Suspicious bugs found!\n":"No suspicious bugs found!\n");
        if(T)
            puts("");
    }
    return 0;
}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

发表回复 取消回复

发表回复取消回复