Codeforces 1082D （贪心）

题面

传送门

分析

贪心

将度限制大于1的点连成一条链，然后将度限制等于1的点挂上去

形状如下图，其中（1,2,3）为度数限制>1的点

显然直径长度=（度数限制>1的节点个数）-1+min(度数限制等于1的节点个数,2)

那么具体如何构造？

首先将度为1和度>1的节点分开

如果有至少1个度为1的节点，就把它作为直径的起点，如图中的4

然后再将度>1的节点全部接上去

再从另一头倒着挂（图中3开始向2,1）剩下的度为1的节点

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define maxn 10005

using namespace std;

int n;

int a[maxn];

struct edge{

	int from;

	int to;

	edge(){

	}

	edge(int u,int v){

		from=u;

		to=v;

	}

	void print(){

		printf("%d %d\n",from,to);

	}

};

vector<edge>ans;

vector<int>l;

int main(){

	int leaf=0;

	scanf("%d",&n);

	int sum=0;

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

		scanf("%d",&a[i]);

		sum+=a[i];

		if(a[i]==1) leaf++;

		if(a[i]==0){

			printf("NO\n");

			return 0;

		}

	}

	if(sum<n*2-2){

		printf("NO\n");

		return 0;

	}

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

		if(a[i]==1){

			l.push_back(i);

			a[i]=0;

		}

	}

	int begin=-1;

	if(l.size()){

		begin=l[l.size()-1];

		l.pop_back();

	}

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

		if(a[i]>1){

			if(begin!=-1){

				a[begin]--;

				a[i]--;

				ans.push_back(edge(begin,i));

			}

			begin=i;

		}

	}

	int t=0;

	for(int i=n;i>=1;i--){

		while(l.size()&&a[i]>0){

			a[i]--;

			ans.push_back(edge(i,l[t++]));

			if(t>=l.size()) break;

		}

		if(t>=l.size()) break;

	}

	int d=(n-leaf)-1+min(2,leaf);

	if(ans.size()==n-1){

		printf("YES %d\n%d\n",d,n-1);

		for(int i=0;i<n-1;i++){

			ans[i].print();

		}

	}else{

		printf("NO\n");

	}

}

巴特西

Codeforces 1082D （贪心）

题面

分析

代码

最新文章

热门文章