ZOJ3732 Graph Reconstruction Havel-Hakimi定理

分析:

给定一个非负整数序列{dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。

进一步，若图为简单图，则称此序列可简单图化 （来自百度百科）

可简单图化的判定可以用Havel-Hakimi定理，然后简述 Havel-Hakimi定理

Havel-Hakimi定理的过程：

1，按度数排序。

2，选取度数最大的点，如果该点度数为0，结束，有解

3，每次选一个度数最大的点，然后将后面的点的度数依次减1，表示该顶点和相应的顶点有边相连，

如果有点的度数减到负数，结束，无解。

4，重复进行步骤1

然后这个题不只是判定有没有解，还需要判断是否有多解

“个人认为此题的难点在于多解时要输出两个。在Havel-Hakimi定理的构造过程中，如果把某两个点“互换”，那么就可以构造出多解的，

那么什么样的两个点才可以互换呢，比如我现在已经排完序，要减的度数序列一直到p，这时，如果p+1的点的度数和p是相同的，

那么p位置和p+1是可以"互换“的，连这两个点中的哪一个都不会影响结果。”（该段文字引用网上某大牛的想法）

所以通过判断p和p+1是否相等，就可以判断是否多解

#include<cstdio>

#include<cstring>

#include<queue>

#include<cstdlib>

#include<algorithm>

#include<vector>

#include<cmath>

using namespace std;

typedef long long LL;

const int N=1e2+;

const int INF=0x3f3f3f3f;

int a[N],d[N],c[N],n;

bool cmp(int x,int y)

{

    return c[x]>c[y];

}

bool check()

{

    for(int i=;i<=n;++i)c[i]=d[i];

    for(int i=; i<=n; ++i)

    {

        sort(a+,a++n,cmp);

        if(!c[a[]])break;

        for(int j=,cnt=; j<=n&&cnt<=c[a[]]; ++j,++cnt)

        {

            --c[a[j]];

            if(c[a[j]]<)return ;

        }

        c[a[]]=;

    }

    return ;

}

struct Edge

{

    int u,v;

} x[N*N];

bool checkmul()

{

    for(int i=; i<=n; ++i)c[i]=d[i];

    for(int i=; i<=n; ++i)

    {

        sort(a+,a++n,cmp);

        if(!c[a[]])break;

        int k=c[a[]]+;

        if(k<=n&&c[a[k]]==c[a[k-]])return ;

        for(int j=,cnt=; j<=n&&cnt<=c[a[]]; ++j,++cnt)

            --c[a[j]];

        c[a[]]=;

    }

    return ;

}

void print()

{

    int tot=;

    for(int i=; i<=n; ++i)c[i]=d[i];

    for(int i=; i<=n; ++i)

    {

        sort(a+,a++n,cmp);

        if(!c[a[]])break;

        for(int j=,cnt=; j<=n&&cnt<=c[a[]]; ++j,++cnt)

        {

            --c[a[j]];

            ++tot;

            x[tot].u=a[],x[tot].v=a[j];

        }

        c[a[]]=;

    }

    for(int i=; i<=tot; ++i)

    {

        printf("%d",x[i].u);

        if(i<tot)printf(" ");

    }

    printf("\n");

    for(int i=; i<=tot; ++i)

    {

        printf("%d",x[i].v);

        if(i<tot)printf(" ");

    }

    printf("\n");

}

int main()

{

    while(~scanf("%d",&n))

    {

        int sum=;

        for(int i=; i<=n; ++i)

        {

            scanf("%d",&d[i]);

            sum+=d[i];

            a[i]=i;

        }

        if(!check())

        {

            printf("IMPOSSIBLE\n");

            continue;

        }

        if(checkmul())

        {

            printf("MULTIPLE\n");

            printf("%d %d\n",n,sum/);

            print();

            printf("%d %d\n",n,sum/);

            for(int i=; i<=n; ++i)c[i]=d[i];

            int tot=;

            bool flag=;

            for(int i=; i<=n; ++i)

            {

                sort(a+,a++n,cmp);

                if(!c[a[]])break;

                if(flag)

                {

                    int k=c[a[]]+;

                    if(k<=n&&c[a[k]]==c[a[k-]])

                        swap(a[k],a[k-]),flag=;

                }

                for(int j=,cnt=; j<=n&&cnt<=c[a[]]; ++j,++cnt)

                {

                    --c[a[j]];

                    ++tot;

                    x[tot].u=a[],x[tot].v=a[j];

                }

                c[a[]]=;

            }

            for(int i=; i<=tot; ++i)

            {

                printf("%d",x[i].u);

                if(i<tot)printf(" ");

            }

            printf("\n");

            for(int i=; i<=tot; ++i)

            {

                printf("%d",x[i].v);

                if(i<tot)printf(" ");

            }

            printf("\n");

        }

        else

        {

            printf("UNIQUE\n");

            printf("%d %d\n",n,sum/);

            print();

        }

    }

    return ;

}