Hard Molecules

给定一个连通图中每个点的度数，求一个满足条件的图，图可以有重边，不能有自环。

n<=5000, d_i<=10⁹

题解

如果不要求图连通，那么只需要判断

\[\sum d_i \mod 2=0\\
\max\{d_i\} \leq \frac{\sum d_i}{2}
\]

然后将度数分成两部分连边即可。

现在要求图连通，那么就先做一棵生成树出来。

由于我们想让每个点的非树边最大度数最小，所以我们可以贪心：维护一棵树，每次选择树上度数最大的点和树外度数最大的点连边。

CO int N=5000+10;

int n,d[N],G[N][N];

IN void connect(int x,int y,int w){

	G[x][y]+=w,G[y][x]+=w;

	d[x]-=w,d[y]-=w;

}

bool vis[N];

bool build_tree(){

	int root=1;

	for(int i=2;i<=n;++i)

		if(d[i]>d[root]) root=i;

	vis[root]=1;

	for(int t=1;t<n;++t){

		int a=-1;

		for(int i=1;i<=n;++i)if(vis[i])

			if(a==-1 or d[i]>d[a]) a=i;

		int b=-1;

		for(int i=1;i<=n;++i)if(!vis[i])

			if(b==-1 or d[i]>d[b]) b=i;

		if(a==-1 or b==-1) return 0;

		if(d[a]==0 or d[b]==0) return 0;

		connect(a,b,1);

		vis[b]=1;

	}

	return 1;

}

typedef pair<int,int> pii;

vector<pii> L,R;

bool check(){

	LL tot=0;

	for(int i=1;i<=n;++i) tot+=d[i];

	if(tot&1) return 0;

	tot>>=1;

	for(int i=1;i<=n;++i)

		if(d[i]>tot) return 0;

	for(int i=1;i<=n;++i)if(d[i]){

		if(tot>=d[i]){

			tot-=d[i];

			L.push_back(pii(d[i],i));

		}

		else{

			if(tot) L.push_back(pii(tot,i));

			R.push_back(pii(d[i]-tot,i));

			tot=0;

		}

	}

	return 1;

}

int main(){

	read(n);

	for(int i=1;i<=n;++i) read(d[i]);

	if(build_tree() and check()){

		puts("Yes");

		for(int i=0,p=0;i<(int)L.size();++i){

			for(;p<(int)R.size() and L[i].first>=R[p].first;++p){

				connect(L[i].second,R[p].second,R[p].first);

				L[i].first-=R[p].first;

			}

			if(L[i].first){

				connect(L[i].second,R[p].second,L[i].first);

				R[p].first-=L[i].first;

			}

		}

		for(int i=1;i<=n;++i,puts(""))

			for(int j=i+1;j<=n;++j) printf("%d ",G[i][j]);

	}

	else puts("No");

	return 0;

}

巴特西

Gym100739H Hard Molecules

Hard Molecules

题解

最新文章

热门文章