图的度数序列相关定理
凄魉
·
·
题解
一张图每个点的度数总和是偶数……
经典问题：给定一个非负整数的序列d,问是否有一个简单图使得每个点的度数恰好为这个序列。可能无解。
首先如果\sum_{i=1}^nd_i是奇数那就铁定无解了，以下默认不会出现这种情况。
Havel-Hakimi 算法
可以贪心的构造，将所有点的度数降序排序，然后每次把度数最大的点1拿出来，向其他度数次大的那些点连边。
度数序列就会从\{d_1,d_2,d_3,d_4,...,d_n\}变到\{d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n\}。
可以证明如果原来的度数序列可简单图化，那么贪心连边后的度数序列也可以简单图化，充分且必要。
Erdős–Gallai 定理
对于非递增度数序列\{d_1,d_2,\dots,d_n\}，如果这个序列可简单化当且仅当
\forall 1\le k\le n,\sum_{i=1}^kd_i\le k(k-1)+\sum_{i=k+1}^nmin(k,d_i)
我也只知道个必要性：右侧展示的其实是前k个点连边的数量上界，k(k-1)是前k个点之间连边的上界，后侧的sigma是前k个点与n-k个点连边的上界。
好像还有个是否有向图化的Fulkerson–Chen–Anstee定理。我也不是很懂……
$$\forall 1\le k\le n,\sum_{i=1}^ka_i\le \sum_{i=1}^kmin(b_i,k-1)+\sum_{i=k+1}^nmin(b_i,k)$$
例题：
[CF1091E New Year and the Acquaintance Estimation](https://www.luogu.org/problemnew/show/CF1091E)
首先介绍这个题我的暴力做法……
第一步则是想到所有度数的和应该要是偶数。
判断加入一个数后这个序列还能不能简单图化，就利用上面那个E定理，这样对于一个序列我们能$O(n)$判断是否能构成一个图。这样的话我们就能枚举答案，在$O(n^2)$时间内解决这个问题了。
但注意到每次向序列中只添加一个数，这个操作对序列的影响是较小的，所以我们考虑加入一个数后序列会有什么变化，并且我们计算的式子有什么变化。
设我们当前加入的一个数为$x$，加入$x$后序列中第一个大于等于$x$的数是原序列中的第$i$大的数。我们要计算每一个$1\le k\le n+1$，上面那个式子是否成立。
那么我们分情况讨论一下：对于$k\le i$，对于这一部分我们计算的式子是
$$\sum_{i=1}^ka_i\le min(x,k)+k(k-1)+\sum_{i=k+1}^nmin(a_i,k)$$
发现式子的变化就只有一个$min$而已，注意到$k$是单调的，所以对于$k\le i$部分的计算又被分成了两部分：
$1\le k\le x$式子是$k+k(k-1)+\sum_{i=k+1}^nmin(a_i,k)-\sum_{i=1}^ka_i$是否$\ge 0$，发现这个式子与$x$无关，所以我们可以预处理这$n$个式子的值，以及前缀最小值。
$x\le k\le i$式子是$x+k(k-1)+\sum_{i=k+1}^nmin(a_i,k)-\sum_{i=1}^ka_i$是否$\ge 0$，我们处理出除去$x$部分的式子的值，我们区间查一个最小值就行了。
接下来是$i<k\le n+1$，也是预处理式子，只不过这一部分的预处理注意插入的数的位置是$i<k$的，小细节注意一下，这一部分也是查一个后缀最小值。
那就没了，具体细节看代码吧。我的复杂度瓶颈是一个区间RMQ，最后的复杂度是$O(NlogN)$，但是注意到询问的区间是$(x,i]$，应该可以从大到小枚举$x$，这样区间就单调了，也就能$O(N)$做了……
另外题解的做法是观察到合法的度数答案一定是一个区间，所以我们可以二分这个答案区间的两个端点，每次去check答案合不合法，这样的话可以很简单的利用单次$NlogN$的check（就是暴力用定理去算），做到$O(Nlog^2N)$，这个做法好写细节少，场上各位巨佬大多都是这么做的。
```
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 520230
#define ll long long
#define ls i<<1
#define rs i<<1|1
#define INF 0x3f3f3f3f3f3f3f3f
int a[N],ans[N],cc;ll sum[N],suf[N],lml[N],lmr[N],lmk[N],tree[N<<2];
bool cmp(int a,int b) {return a>b;}
void build(int i,int l,int r)
{
if (l==r) {tree[i]=lml[l];return;}
int mid=l+r>>1;
build(ls,l,mid);build(rs,mid+1,r);
tree[i]=min(tree[ls],tree[rs]);
}
ll query(int i,int l,int r,int L,int R)
{
if (L<=l&&r<=R) return tree[i];
int mid=l+r>>1;
if (R<=mid) return query(ls,l,mid,L,R);
else if (L>mid) return query(rs,mid+1,r,L,R);
return min(query(ls,l,mid,L,R),query(rs,mid+1,r,L,R));
}
inline int read(){
int n=0;char a;bool z=false;
while(a=getchar())
{
if (a>'9'||a<'0')
if (z) break;
else continue;
if (!z) z=true;
n=(n<<1)+(n<<3)+(a^48);
}
return n;
}
int main()
{
int n=read();bool Z=false;
for (int i=1;i<=n;++i) a[i]=read();
sort(a+1,a+1+n,cmp);
for (int i=n;i;--i) suf[i]=suf[i+1]+a[i];
for (int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
for (int i=1,j=n;i<=n;++i)
{
while(j&&a[j]<i) --j;
if (j>i) lml[i]=1ll*(j-1)*i+suf[j+1]-sum[i];
else lml[i]=suf[i+1]+1ll*i*(i-1)-sum[i];
lmk[i]=lml[i]+i;
}
for (int i=0,j=n;i<=n;++i)
{
while(j&&a[j]<i+1) --j;
if (j>i) lmr[i]=1ll*j*(i+1)-sum[i]+suf[j+1];
else lmr[i]=suf[i+1]+1ll*i*(i+1)-sum[i];
}
build(1,1,n);
lmk[0]=INF;for (int i=1;i<=n;++i) lmk[i]=min(lmk[i-1],lmk[i]);
lmr[n+1]=INF;for (int i=n;i>=0;--i) lmr[i]=min(lmr[i],lmr[i+1]);
for (int x=sum[n]&1,i=n;x<=n;++++x)
{
while(i&&x>a[i]) --i;Z=true;
if (lmk[min(i,x)]<0) continue;
if (x<i&&query(1,1,n,x+1,i)<-x) Z=false;
if (!Z) continue;
if (lmr[i]<x) Z=false;
if (Z) ans[++cc]=x;
}
if (!cc) return !printf("-1");
for (int i=1;i<=cc;++i) printf("%d ",ans[i]);
return 0;
}
//by qlwpc
```cpp