zoj 3732 Graph Reconstruction(构造) - c++编程基础

先跑一遍Havel_Hakimi算法判断是否有解。对于判断多解的情况，再跑一遍Havel_Hakimi，如果sort(p+i, p+n)排序后，从i分别向i+1, i+2...i+p[i].d连边时，如果i+p[i].d跟i+p[i].d+1的剩余度数相同，那么交换这两个点在剩下的图中的位置，就能得到两个不同的图了。

坑：当边数为零的时候，也要输出两个空行...开始还以为第一组输出是打印错误呢....

#include  
#include  
#include  
#define REP(i, n) for(int i=0; i e1[maxm], e2[maxm];  
struct Node  
{  
    int d, id;  
    bool operator < (const Node& rhs) const  
    {  
        return d > rhs.d;  
    }  
}p[2][maxn];  
  
void print(pair *e)  
{  
    printf("%d %d\n", n, tot);  
    REP(i, tot) printf("%d%c", e[i].first, i == tot-1   '\n' : ' ');  
    REP(i, tot) printf("%d%c", e[i].second, i == tot-1   '\n' : ' ');  
    if(tot == 0) printf("\n\n");  
}  
  
bool solve(Node *p, pair *e)  
{  
    int cnt = 0;  
    REP(i, n-1)  
    {  
        sort(p+i, p+n);  
        if(p[i].d+i > n-1) return false;  
        for(int j=i+1; j <= p[i].d+i; j++)  
        {  
            if(--p[j].d < 0) return false;  
            e[cnt++] = make_pair(p[i].id+1, p[j].id+1);  
        }  
    }  
    return p[n-1].d == 0;  
}  
  
bool gao(Node *p, pair




 *e)  
{  
    int cnt = 0, ret = 0;  
    REP(i, n-1)  
    {  
        sort(p+i, p+n);  
        int tmp = p[i].d + i;  
        if(tmp < n-1 && p[tmp].d == p[tmp+1].d && p[tmp].d != 0)  
        {  
            ret = 1;  
            swap(p[tmp].id, p[tmp+1].id);  
        }  
        for(int j=i+1; j<=tmp; j++)  
            p[j].d--, e[cnt++] = make_pair(p[i].id+1, p[j].id+1);  
    }  
    return ret;  
}  
  
int main()  
{  
    while(~scanf("%d", &n))  
    {  
        tot = 0;  
        REP(i, n)  
        {  
            scanf("%d", &p[0][i].d);  
            p[0][i].id = i;  
            p[1][i] = p[0][i];  
            tot += p[0][i].d;  
        }  
        if(tot&1) puts("IMPOSSIBLE");  
        else  
        {  
            tot /= 2;  
            if(!solve(p[0], e1)) puts("IMPOSSIBLE");  
            else  
            {  
                if(gao(p[1], e2))  
                {  
                    puts("MULTIPLE");  
                    print(e1);  
                    print(e2);  
                }  
                else  
                {  
                    puts("UNIQUE");  
                    print(e1);  
                }  
            }  
        }  
    }  
    return 0;  
}