CodeForces 1082 D Maximum Diameter Graph

题意：现在有n个点，每个点的度数最大为di，现在要求你构成一棵树，求直径最长。

题解：把所有度数为2的点先扣出来，这些就是这颗树的主干，也就是最长的距离。

然后我们把度数为2的点连起来，之后就处理1的点，先在主干的最左边和最右边加上新的点，这样可以使得直径边长。

然后其他的点随便放就好了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod =  (int)1e9+7;
const int N = 1e5 + 100;
pll p[N];
int d[N];
vector<int> vc[2];
vector<pll> ans;
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &d[i]);
        if(d[i] > 1) vc[1].pb(i);
        else vc[0].pb(i);
    }
    if(vc[1].size() == 0){
        puts("NO");
        return 0;
    }
    int fans = 0;
    for(int i = 1; i < vc[1].size(); ++i){
        ans.pb({vc[1][i], vc[1][i-1]});
        --d[vc[1][i]], --d[vc[1][i-1]];
        ++fans;
    }
    int p = 0;
    for(int j = 0; j < vc[0].size(); ++j){
        if(j == 0){
            if(d[vc[1][0]]){
                --d[vc[1][0]];
                ++fans;
                ans.pb({vc[0][j], vc[1][0]});
            }
        }
        else if(j == 1){
            if(d[vc[1][vc[1].size()-1]]){
                --d[vc[1][vc[1].size()-1]];
                ++fans;
                ans.pb({vc[0][j], vc[1][vc[1].size()-1]});
            }
        }
        else {
            while(p < vc[1].size() && d[vc[1][p]] == 0) ++p;
            if(p == vc[1].size()) break;
            --d[vc[1][p]];
            ans.pb({vc[0][j], vc[1][p]});
        }
    }
    if(p ==  vc[1].size()) puts("NO");
    else {
        printf("YES %d\n", fans);
        printf("%d\n", ans.size());
        for(int i = 0; i < ans.size(); ++i){
            printf("%d %d\n", ans[i].fi, ans[i].se);
        }
    }
    return 0;
}

View Code

CodeForces 1082 D Maximum Diameter Graph

推荐阅读