[TIOJ] 1210. 圖論 之 簡單圖測試

題目連結:http://tioj.infor.org/problems/1210

---

其實一開始我在寫這題的時候真的想不出來怎麼做，是看了黃信元學長的文才知道的。
本題有兩個定理可以拿來應用，我一開始都只有找到Havel定理的用法，雖然他的複雜度是$O(n^2 log n)$，不過本題還是可以過，所以就稍微講一下他的做法吧，每次都把degree最大的拿出來(假定其degree為k)，則把他跟後k大的所有點連邊，也就是把他後k個的值都減一，並把自己改成零，重複這件事直到出現負數(表示不合法)，或全部都變成0(合法)為止，所以做完後也構造完整張圖了，不過複雜度真的不夠好。
另外一個定理是Erdős–Gallai 定理，我覺得沒那麼直覺，他是要驗證從大到小排序後的$d_k$ $$\forall k,1 \leq k \leq n, \mathop{\sum_{i=1}^{k}} d_i \leq ( k(k-1) + \mathop{\sum_{j=k+1}^{n}} min(k, d_j) )$$ 不過照著定理裸裸的定義做可能會變成$O(n^2)$，不過仔細想想後會發現因為k有單調性，且$d_j$也有單調性，所以當超過一定範圍後，$d_j$就必定小於k，其餘都會是k，而且那個範圍一定會越來越前面，所以可以先處理後綴和後在每次算前先找到那個範圍，之後直接取後綴和就好了，不過仔細想想連後綴和都不需要預處理，在找範圍時就可以好好算了，但因為區間閉開開閉之類的一直讓我有點卡卡的，所以我就沒寫那種常數優化了，反正複雜度都還是$O(n)$

---

Havel定理版本

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;

int vv[10005];

int main(){
	cin.tie(0);std::ios_base::sync_with_stdio(0);
	int n;
	cin>>n;
	while(n!=0){
		int k=0;
		for(int i=0;i<n;i++){
			int a;
			cin>>a;
			k=(a+k)%2;
			vv[i]=a;
		}
		if(k){
			cout<<"No\n";
		}else{
			bool flag=1;
			sort(vv,vv+n,[](int a,int b){return a>b;});
			for(int i=0;i<n;i++){
				for(int j=1;j<=vv[0];j++){
					vv[j]--;
					if(vv[j]<0){
						flag=0;
						break;
					}
				}
				if(!flag) break;
				vv[0]=0;
				sort(vv,vv+(n-i),[](int a,int b){return a>b;});
			}
			if(flag) cout<<"Yes\n";
			else cout<<"No\n";
		}
		cin>>n;
	}
}

---

Erdős–Gallai 定理

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::sort;
using std::min;
using std::max;

int vv[10006],n,cnt[10006];

int main(){
	cin.tie(0);std::ios_base::sync_with_stdio(0);
	cin>>n;
	while(n!=0){
		int k=0;
		for(int i=1;i<=n;i++){
			int a;
			cin>>a;
			k=(a+k)%2;
			vv[i]=a;
		}
		if(k){
			cout<<"No\n";
		}else{
			long long ss=0;
			bool flag=1;
			sort(vv+1,vv+1+n,[](int a,int b){return a>b;})
			for(int i=1;i<=n;i++){
				ss+=vv[i];
				long long oao=i*(i-1);
				for(int j=i+1;j<=n;j++)
					oao+=min(i,vv[j]);
				if(ss>oao){
					flag=0;
					break;
				}
			}
			if(flag) cout<<"Yes\n";
			else cout<<"No\n";
		}
		cin>>n;
	}
}

---

優化的 Erdős–Gallai 定理

#include <iostream>
#include <algorithm>
using std::cin;
using std::cout;
using std::max;

int deg[10005],count[10005],posfixSum[10005];
int n;

inline void cSort();
inline void init(int);

int main(){
	cin.tie(0);std::ios_base::sync_with_stdio(0);
	while(cin>>n,n!=0){
		init(n);
		int k=0;
		for(int i=1;i<=n;i++){
			cin>>deg[i];
			k=(deg[i]+k)%2;
		}
		if(k){
			//預判度數和不為偶數時會不成一張圖
			cout<<"No\n";
		}else{
			bool flag=1;
			cSort();
			//計數排序
			int sumD=0,firstG=n;
			posfixSum[n+1]=0;
			for(int i=n;i>=0;i--) posfixSum[i]=deg[i]+posfixSum[i+1];
			//預處理後綴和
			for(int i=1;i<=n;i++){
				sumD+=deg[i];
				while(firstG>=i&&deg[firstG]<i) firstG--;
				while(firstG<i) firstG++;
				//找到最遠多少開始min(k,d[j])=d[j];
				int det=i*(i-1)+posfixSum[firstG+1]+(firstG-i)*i;
				if(sumD>det){
					flag=0;
					break;
				}
			}
			cout<<(flag?"Yes\n":"No\n");
		}
	}
}

inline void cSort(){
	int mx=-1;
	for(int i=1;i<=n;i++){
		count[deg[i]]++;
		mx=max(mx,deg[i]);
	}
	for(int i=mx,j=1;i>=0;i--){
		while(count[i]>0){
			deg[j++]=i;
			count[i]--;
		}
	}
}

inline void init(int n){
	for(int i=1;i<=n;i++){
		count[i]=0;
		posfixSum[i]=0;
	}
}