所謂蘭道定理，就是蘭道定下的道理

（逃）

解析

每條邊被規定了方向的完全圖叫做競賽圖
競賽圖中，設每個點的出度為$u_i$
顯然有：
$$\sum u_i=\frac{n\times (n?1)}{2}$$
而蘭道定理的內容是：
若n個點的出度序列升序排序后為$s_i$，那么其能構成競賽圖的充要條件是，對于任意的k屬于[1,n]，都有：
$$\sum _{i=1}^k{s}_i>=\frac{k\times (k?1)}{2}$$

當且僅當k=n時，取等
必要性比較顯然，現在的關鍵是充分性
蘭道定理的證明類似于裴蜀定理，是一種構造的方法
先構造出一個競賽圖 $T$ ，滿足任意一點 i 都只對比自己編號小的點連邊，設其出度為$u_i$
顯然，$u_i=i?1$
然后考慮如下操作：

找到第一個位置，使得$s_i>u_i$，設為 $x$

找到最靠后的 $y$ ，滿足 $s_x=s_y$（xy可以相等）

找到第一個位置，使得 $s_i<u_i$ 設為 $z$

此時由于$u_z>s_z>=s_y>u_y$，可以得出，$u_z?u_y>=2$，因此，一定存在第三個點p，使得z連向p且p連向y

調換$(z,p)$和$(y,p)$的方向，此時只有$u_z$減小1，$u_y$增大1，而$u_p$不變

不斷重復以上流程，直到$u$和$s$完全相同

代碼

CF850D：Tournament Construction

#include<bits/stdc++.h> using namespace std; const int N=3e5+100; const int mod=1e9+7; double eps=1e-10; #define ll long long ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();};while(isdigit(c)){x=x*10+c-'0';c=getchar();};return x*f; }int n,m;int dp[35][100][2050],num[35][100][2050]; int a[35],pre[35]; int u[2005],s[2005],tot; void find(int k,int x,int w){if(k==0) return;find(k-1,x-num[k][x][w],w-num[k][x][w]*a[k]);for(int i=1;i<=num[k][x][w];i++) s[++tot]=a[k];return; } bool jd[2050][2050]; inline void rev(int x,int y){if(jd[x][y]){u[x]--;u[y]++;}else{u[y]--;u[x]++;}jd[x][y]^=1;jd[y][x]^=1; } int main(){#ifndef ONLINE_JUDGE//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);#endifn=read();for(int i=1;i<=n;i++) a[i]=read();sort(a+1,a+1+n);dp[0][0][0]=1;int k(0);for(k=1;;k++){for(int i=1;i<=n;i++){if(i>k) break;for(int w=k*(k-1)/2;w<=2000;w++){for(int j=1;j<=k&&j*a[i]<=w;j++){if(dp[i-1][k-j][w-j*a[i]]){num[i][k][w]=j;dp[i][k][w]=1;}}}}if(dp[n][k][k*(k-1)/2]) break;}//printf("ok k=%d\n",k);find(n,k,k*(k-1)/2);//for(int i=1;i<=k/2;i++) swap(s[i],s[k-i+1]);for(int i=1;i<=k;i++) u[i]=i-1;for(int i=1;i<=k;i++){for(int j=1;j<i;j++) jd[i][j]=1;}while(1){int x(0),y(0),z(0),p(0);//for(int i=1;i<=k;i++) printf("%d ",s[i]);putchar('\n');//for(int i=1;i<=k;i++) printf("%d ",u[i]);putchar('\n');for(int i=1;i<=k;i++){if(s[i]>u[i]){x=i;break;}}if(!x) break;y=x;for(int i=x+1;i<=k;i++) if(u[i]==u[x]) y=x;for(int i=k;i>=1;i--) if(u[i]>s[i]) z=i;//printf("x=%d y=%d z=%d\n",x,y,z);for(p=1;p<=k;p++){if(jd[z][p]&&!jd[y][p]){//printf("x=%d y=%d z=%d p=%d\n",x,y,z,p);rev(z,p);rev(y,p);break;}}}printf("%d\n",k);for(int i=1;i<=k;i++){for(int j=1;j<=k;j++){printf("%d",jd[i][j]);}putchar('\n');}return 0; } /* 2 3 7 4 9 9 1 2 8 3 1 4 2 4 */

總結

以上是生活随笔為你收集整理的兰道定理（竞赛图）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。