Havel定理

将顶点进行排序,去掉度m最大的点,依次让其后m个数减1,若后面的某个顶点出现负数的情况或后面的数的个数少于最大的度

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;

struct EDGE
{
    int d;//储存度数
    int num;//储存位置
}edge[15];

bool cmp(EDGE x,EDGE y)
{
    return x.d>y.d;
}

int main()
{
    int T,n,i,j;
    int d[15][15];
    scanf("%d",&T);
    while(T--)
    {
        int flag=1;
        memset(d,0,sizeof(d));
        scanf("%d",&n);
        for (i=0;i<n;i++)
        {
            edge[i].num=i;
            scanf("%d",&edge[i].d);
        }
        sort(edge,edge+n+1,cmp);//这个很重要,若度数大于后面剩余的数的时候多家进去的那个就其做作用两人
        while (edge[0].d && edge[n-1].d>=0)//  排序后若某个点的度数为负数就不用判断后的了
        {  
            int i = 1;  
            while (edge[0].d--)  
            {  
                --edge[i].d;  
                d[edge[0].num][edge[i].num] = 1;  
                d[edge[i].num][edge[0].num] = 1;  
                ++i;  
            }  
            ++edge[0].d;  
            sort(edge,edge+n,cmp);  
        }  
        
        if(edge[n-1].d<0) 
        {
            printf("NO\n\n");
            continue;
        }
        printf("YES\n");
        for (i=0;i<n;i++)
        {
            for (j=0;j<n;j++)
            {
                if(j) printf(" %d",d[i][j]);
                else printf("%d",d[i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POj 1797 Heavy Transportation

    题意:求从1-n所能承受的最大重量是多少,其最大重量就是1-n通路的最小边 分析:求最大生成树的最小边,排序的时候按照权值从大到小派,然后生成树,知道找到1-n...

    用户1624346
  • 强连通专题

    求割点(无向边): 所谓的割点,就是删除某个点,图便不连通了。  POJ  1523 #include<stdio.h> #include<string.h> ...

    用户1624346
  • Plus One

    问题:数组模拟整数加1 class Solution { public: vector<int> plusOne(vector<int> &digits...

    用户1624346
  • 解密"秒杀"软件 | JavaScript最佳入门案例用javascript实现秒杀倒计时的效果chrome "奇技淫巧" 之 脚本编辑器!

    网上购物变得的越来普遍,各种"秒杀"抢购的活动越来越多,除了早年雷布斯的"饥饿营销",大多数秒杀活动还是有货源的,我们秒不到货,大多是因为我们败给了计算机脚本...

    zhaoolee
  • P3275 [SCOI2011]糖果

    题目描述 幼儿园里有N个小朋友,lxhgww老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明...

    attack
  • P3376 【模板】网络最大流

    题目描述 如题,给出一个网络图,以及其源点和汇点,求出其网络最大流。 输入输出格式 输入格式: 第一行包含四个正整数N、M、S、T,分别表示点的个数、有向边的个...

    attack
  • 解决 Eclipse 下的控制台输出乱码 问题

    1、打开对应的 Run Configuration /Debug Configuration 窗口

    LeoXu
  • 基于事件驱动的微服务模式

    本文我们将讨论一些经常用在微服务应用中可扩展的设计模式: 事件流 事件溯源 通晓多语言的持久性 内存镜像 命令查询职责分离 起因 Uber, Gilt和其它的公...

    用户1263954
  • 大数据和分布式入门:主流分布式缓存组件

    在大数据处理当中,核心指导思想始终是分布式,基于分布式思想,我们有了Hadoop等开源技术框架,能够以更低的成本完成企业大数据系统平台搭建,支持业务进展。今天大...

    成都加米谷大数据
  • 【大型网站技术架构笔记】(二)大型网站架构模式与核心要素

    即对系统进行横向划分。比如进行MVC分层,又可分为接入层、业务层、核心数据层。应当禁止跨层调用以及逆向调用。

    吃橙子的狐狸

扫码关注云+社区

领取腾讯云代金券