POJ1659 Frogs' Neighborhood(Havel–Hakimi定理)

时间：2024-11-13 15:36:26

题意

题目链接

\(T\)组数据，给出\(n\)个点的度数，问是否可以构造出一个简单图

Sol

Havel–Hakimi定理：

  • 给定一串有限多个非负整数组成的序列，是否存在一个简单图使得其度数列恰为这个序列。

令\(S=(d_1,d_2,\dots,d_n)\)为有限多个非负整数组成的非递增序列。 S可简单图化当且仅当有穷序列\(S’=(d_2-1,d_3-1,...,d(d_1+1)-1,d(d_1+2),...,d_n)\)只含有非负整数且是可简单图化的。

最后判断一下是否都是零就好了

感觉这个算法。。就是个贪心吧。。

当然判断这类问题的可行性还有另外一种方法：Erdős–Gallai定理

令\(S=(d_1,d_2,...,d_n)\)为有限多个非负整数组成的非递增序列。\(S\)可简单图化当且仅当这些数字的和为偶数，并且

\(\sum_{i = 1}^k d_i \leqslant k(k - 1) + \sum_{i = k + 1}^n min(d_i, k)\)

对所有\(1 \leqslant k \leqslant n\)都成立

不过这个好像没办法输出方案？？。。。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#define Pair pair<int, int>

#define MP(x, y) make_pair(x, y)

#define fi first

#define se second

using namespace std;

const int MAXN = 1e5 + 10, INF = 1e9 + 7;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int T, N, reach[101][101], sum = 0;

Pair a[MAXN];

void init() {

    memset(reach, 0, sizeof(reach));

    sum = 0;

}

int main() {

//  freopen("a.in", "r", stdin);

    T = read();

    while(T--) {

        init();

        N = read();

        for(int i = 1; i <= N; i++) a[i] = MP(read(), i), sum += a[i].fi;

        if(sum % 2 != 0) {puts("NO\n"); continue;}

        bool f = 0;

        for(int i = 1; i <= N; i++) {

            sort(a + i, a + N + 1, greater<Pair>());

            if(a[i].fi <=  0) continue;

            for(int j = i + 1; j <= i + a[i].fi; j++) a[j].fi -= 1, reach[a[i].se][a[j].se] = 1, reach[a[j].se][a[i].se] = 1;

            a[i].fi = 0;

        }

        for(int i = 1; i <= N; i++) if(a[i].fi != 0) {puts("NO\n"); f = 1; break;}

        if(f) continue;

        puts("YES");

        for(int i = 1; i <= N; i++, puts(""))

            for(int j = 1; j <= N; j++)

                printf("%d ", reach[i][j]);

        puts("");

    }

}

/*

1

6

4 3 1 4 2 0

*/

相关文章