题解 CF1082D Maximum Diameter Graph

题解-CF1082D Maximum Diameter Graph

• 题目大意

就是让你构造一连通的无向图,使得每个点的度数并且要使得直径足够长。

贪心： 要让直径最长我们就要构造链，对于的点把他们加到链上去。然后把那些度为的点粘到链上去。最后一点也是最值得注意的是：我们还可以让链变得更加长，就是把那个度为一点（如果存在）粘到链的两端。这样就可以保证树的直径最长。正确性很显然。

对于那些不合法情况也就两种：

所有点的都为

存在还没有被匹配到的点

剩下的就是细节问题了。

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,a,b) for ( int i=(a);i>=(b);i-- )
#define FOR(i,t) for ( int i=head[t];i;i=E[i].nex )
//#define int long long
#define db double
#define mem(x,s) memset(x,s,sizeof(x))
#define cpy(x,s) memcpy(x,s,sizeof(x))
#define lowbit(x) x&(-x)
using namespace std;

namespace IO {
    #define gc getchar
    #define pt putchar
    inline int read() {
        int sum=0,ff=1; char ch=gc();
        while(!isdigit(ch)) {
            if(ch=='-') ff=-1;
            ch=gc();
        }
        while(isdigit(ch))
            sum=sum*10+(ch^48),ch=gc();
        return sum*ff;
    }

    inline void write(int x) {
        if(x<0) pt('-'),x=-x;
        if(x>9) write(x/10);
        pt(x%10|48);
    }

    inline void wln(int x) {
        write(x); pt('\n');
    }

    inline void wrn(int x) {
        write(x); pt(' ');
    }
}

using namespace IO;

const int N=505;
const int M=N*N;

int n,m,du[N],tmp[N],G[N][N];
int tot,ans,md,Du[N],e[M][3];
int head[N],cnt,rt,one[N],s;
struct nood {
    int nex,to,w;
};
nood E[M];

inline void jia(int u,int v) {
    E[++cnt]=(nood){head[u],v};
    head[u]=cnt;
}

inline void dfs(int u,int fa,int dep) {
    if(dep>md) {
        md=dep;
        rt=u;
    }
    FOR(i,u) {
        int v=E[i].to;
        if(v==fa) continue;
        dfs(v,u,dep+1);
    }
}

int main() {
    n=read();
    For(i,1,n) {
        int s=read();
        du[i]=s;
        if(s==1) one[++s]=i;
    }
    if(one[1]) tmp[1]=one[1];
    For(i,1,n) if(du[i]!=1) tmp[++tot]=i;
    if(one[2]) tmp[++tot]=one[2];
    if(!tot) return printf("NO\n"),0;
    For(i,1,tot-1) {
        e[++m][0]=tmp[i];
        e[m][1]=tmp[i+1];
        Du[tmp[i]]+=1;
        Du[tmp[i+1]]+=1;
        G[tmp[i]][tmp[i+1]]=G[tmp[i+1]][tmp[i]]=1;
    }
    For(i,1,tot) if(du[tmp[i]]>=2) {
        if(Du[tmp[i]]>=du[tmp[i]]) continue;
        For(j,1,n) 
            if(du[j]==1&&j!=tmp[i]&&!G[j][tmp[i]]) {
                if(Du[j]>=du[j]) continue;
                if(Du[tmp[i]]>=du[tmp[i]]) continue;
                e[++m][0]=tmp[i];
                e[m][1]=j;
                Du[tmp[i]]+=1;
                Du[j]+=1;
            }
    }
    For(i,1,n) if(!Du[i]) return printf("NO\n"),0;
    printf("YES ");
    For(i,1,m) jia(e[i][0],e[i][1]),jia(e[i][1],e[i][0]);
    dfs(1,0,0);
    md=0;
    dfs(rt,0,0);
    wln(md);
    wln(m);
    For(i,1,m) wrn(e[i][0]),wln(e[i][1]);
    return 0;
}