专栏首页数据结构与算法POJ1659 Frogs' Neighborhood(Havel–Hakimi定理)

POJ1659 Frogs' Neighborhood(Havel–Hakimi定理)

题意

题目链接

\(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 
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1074 食物链 2001年NOI全国竞赛

    1074 食物链 2001年NOI全国竞赛 时间限制: 3 s 空间限制: 64000 KB 题目等级 : 钻石 Diamond 题目描述 Des...

    attack
  • cf375D. Tree and Queries(莫队)

    具体实现的时候可以直接用\(tim[i]\)表示第\(i\)个颜色的出现次数,\(ans[i]\)表示出现次数多于\(i\)的颜色的种类

    attack
  • 网络最大流算法—EK算法

    前言 EK算法是求网络最大流的最基础的算法,也是比较好理解的一种算法,利用它可以解决绝大多数最大流问题。 但是受到时间复杂度的限制,这种算法常常有TLE的风险 ...

    attack
  • cigarettes

    Tom has many cigarettes. We hypothesized that he has n cigarettes and smokes the...

    书童小二
  • codevs原创抄袭题 5960 信使

    题目描述 Description  •战争时期,前线有n个哨所,每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息,当然,这是要花费一定时...

    attack
  • Wordpress <= 4.9.6 任意文件删除漏洞

    本文转载自:Wordpress <= 4.9.6 任意文件删除漏洞 -http://blog.vulnspy.com/2018/06/27/Wordpress-...

    Ambulong
  • 提高性能,MySQL 读写分离环境搭建(二)

    上篇文章和大家聊了 CentOS7 安装 MySQL5.7 ,这个大家一般装在虚拟机里边,装好了,把虚拟拷贝一份,这样我们就有两个 MySQL ,就可以开始今天...

    江南一点雨
  • net/rpc

    比如我们在服务器注册一个对象,这个对象可以作为一项服务被暴露,服务的名字就是该对象的类型名,注册之后,对象的导出方法就可以被远程访问。服务端可以注册多个不同类型...

    酷走天涯
  • Windows 10下安装Docker Desktop

    安装连接:https://hub.docker.com/editions/community/docker-ce-desktop-windows/

    Jerry Wang
  • SAP SD-销售订单页签信息介绍

    PR01,合同的定价;ZDI1,合同价格未确定时的价格;ZML1,产品目录价;VPRS,成本价; 当合同价格未确定时,PR01的值和ZDI1的值...

    用户5495712

扫码关注云+社区

领取腾讯云代金券