自动搬运

查看原文

来自洛谷，原作者为

	Otomachi_Una_ We will never forget those days, thanks for everything.

搬运于2025-08-24 22:57:58，当前版本为作者最后更新于2024-10-14 21:57:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【题目简述】

构造一个 $n$ 个点，$m$ 个三元环的竞赛图。

$n\leq 5000$。

【解题思路】

经典结论：竞赛图三元环只和每个点的入度序列有关。

不难发现当入度序列为 $[0,1,\dots,n-1]$ 时没有三元环，当把一对 $(x,x+2)$ 调整为 $(x+1,x+1)$ 时会多一个三元环。

直接调整复杂度是 $\mathcal O(M)$ 的。可以考虑找一个最小的 $n_0\leq n$ 使得其最大三元环量不小于 $M$，在 $n_0$ 基础上调整，其余连成 DAG 即可。

时间复杂度：$\mathcal O(n^2)$。

【参考代码】

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=5005;
int n,d[MAXN];ll m;
bool ans[MAXN][MAXN];
ll max_reach(ll x){
	ll r=x*((x-1)/2)*(x/2);
	return (r-x*(x-1)*(x-2)/6)/2;
}
void solve(){
	cin>>n>>m;
	if(m>max_reach(n)){
		cout<<"No\n";
		return;
	}
	cout<<"Yes\n";
	for(int i=1;i<=n;i++) d[i]=i-1;
	for(int i=1;i<=n;i++) if(m<=max_reach(i)){
		m=max_reach(i)-m;
		if(i%2==1) for(int j=1;j<=i;j++) d[j]=(i-1)/2;
		else for(int j=1;j<=i;j++) d[j]=i/2-(j<=i/2);
		while(m){
			for(int l=1,r=1;r<n;l=r+1){
				r=l;
				while(r<i&&d[r+1]==d[r]) r++;
				int r0=r;
				while(m>0&&l<r){
					m--;
					d[l++]--,d[r--]++;
				}
				r=r0;
			}
		}
		break;
	}
	sort(d+1,d+n+1);
	// for(int i=1;i<=n;i++) cout<<d[i]<<" \n"[i==n];
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) ans[i][j]=0;
	for(int i=n;i>=2;i--){
		d[i]=i-1-d[i];
		for(int l=i-1,r=i-1;;r=l-1){
			l=r;
			while(l>1&&d[l]==d[l-1]) l--;
			for(int j=l;j<=r;j++){
				if(d[i]>0) d[i]--,d[j]--,ans[j][i]=1;
				else ans[i][j]=1;
			}
			if(l==1) break;
		}
		// if(d[i]) cerr<<"ERROR "<<i<<' '<<d[i]<<endl;
	}
	for(int i=2;i<=n;i++) for(int j=1;j<i;j++){
		cout<<ans[i][j];
		if(j==i-1) cout<<'\n';
	}
}
int main(){
	ios::sync_with_stdio(false);
	// freopen("Otomachi_Una.in","r",stdin);
	// freopen("Otomachi_Una.out","w",stdout);
	int _;cin>>_;
	while(_--) solve();
	return 0;
}