首页 > 代码库 > UESTC 913 握手 Havel定理+优先队列
UESTC 913 握手 Havel定理+优先队列
给定一个非负整数序列{dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化。
此题因为是无自环无重边，所以是简单图。用判定简单图可图化的Havel-Hakimi定理。
Havel-Hakimi定理：
一个度序列：
是简单图度序列当且仅当：
是简单图的度序列。
简单来讲，算法流程如下：
设度序列为d1,d2,d3....dn
1.如果度序列中元素有负数或者度序列和不为偶数，则肯定不可图。
2.每次取度序列中最大元素，设为M,如果M>n-1（n为此时的元素数），则不可图。否则取次大的M个元素，将他们都减1，再次加入到度序列中，元素数减1，如此往复，直到：
（1）度序列出现负数元素，则不可图，退出。
（2）度序列全为0，则可图，退出。
回到题目，这题由于n过大（10^5），所以不能每次都排序来找前M大的数，所以考虑用优先队列来实现高效的插入，排序，取最大元素等操作。
（优先队列的复杂度）
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>#include <queue>#include <functional>using namespace std;#define N 100007priority_queue<int,vector<int>,less<int> > que;queue<int> tmp;int check(int n){ int dmax,k,i; while(1) { dmax = que.top(); que.pop(); if(dmax > n-1) return 0; while(dmax--) { k = que.top(); que.pop(); k--; if(k < 0) return 0; tmp.push(k); } while(!tmp.empty()) { k = tmp.front(); tmp.pop(); que.push(k); } dmax = que.top(); if(dmax == 0 || n == 1) break; n--; } return 1;}int main(){ int t,n,i,x; scanf("%d",&t); while(t--) { while(!que.empty()) que.pop(); while(!tmp.empty()) tmp.pop(); scanf("%d",&n); int flag = 1; int sum = 0; for(i=0;i<n;i++) { scanf("%d",&x); if(x < 0) flag = 0; que.push(x); sum += x; } if(!flag || sum%2) { puts("NO"); continue; } flag = check(n); if(flag) puts("YES"); else puts("NO"); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。