[Codeforces 1082D] Maximum Diameter Graph

[Codeforces 1082D] Maximum Diameter Graph

문제 설명 : 

n개의 vertex에 대해서 각 vertex당 최대로 연결 가능한 degree의 수가 주어진다. 그 degree 이내에서 만들 수 있는 그래프 중에서 지름의 길이가 가장 길도록 그래프를 만들 때, 지름의 길이와 그 때의 간선 연결 관계를 출력하는 문제이다.

풀이 : 

이 문제에서 가장 먼저 생각해야 할 점은 '지름의 길이를 최대가 되도록'해야한다. 어떻게 하면 최대가 될까? 일단 그래프를 반드시 트리의 형태로 만들어야 한다. 사이클이 생기는 그래프는 지름의 길이가 짧아질 수도 있다. 

트리로 만들겠다고 방향을 잡은 뒤에 생각할 것은 vertex들을 어떻게 연결해야 지름이 가장 길어질 것인가에 대한 생각이다. 

degree가 2이상인 vertex끼리 연결해서 뼈대가 되는 트리를 먼저 구성한 다음에 이 트리에 양 끝에 1인 vertex를 붙여주면 된다. 나머지 1인 vertex들은 각 vertex들의 degree에 맞게 아무렇게나 이어주면 된다

주의할 점 :

(3/2 2 2) 처럼 입력 조건에서 degree가 1인 vertex가 주어지지 않을 수도 있다. 트리를 구성하기 위해서는 degree가 1인 vertex가 최소 2개는 존재해야 한다. 따라서 1짜리가 2개미만이라면 어떤 degree를 줄여서 1로 만들어야한다. 이때 아무거나 줄이면 sum값이 2n-2보다 작아질 수도 있기 때문에 degree가 가장 작은 vertex들을 찾아서 그것들을 줄여야 한다.

배운 점 :

그래프(트리)에서 degree가 1이면 리프노드가 된다. 지름을 최대화 하기 위해서는 degree가 2이상인 것들을 쭉 늘어놓고 1을 양 끝에 붙이면 된다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
/****************************Contest Template******************************/
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
typedef long long ll;
typedef unsigned long long ull;
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
/****************************Contest Template******************************/
const int SIZE= 509;
 
int arr[SIZE];
vector<int> _1,_2;
 
int main(){
    int n;  scanf("%d",&n);
    int sum=0,cnt_1=0;
 
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
        sum+=arr[i];
        if(arr[i]==1) {
            cnt_1++;
            _1.push_back(i);
        }
    }
    if(sum<2*(n-1)){
        printf("NO\n");
        return 0;
    }
 
    printf("YES %d\n",n-max(2,cnt_1)+1);
    printf("%d\n",n-1);
 
    int min1,min2,idx1=0,idx2=0;
    min1=min2=1<<30;
 
    if(cnt_1<2){
        for(int i=1 ; i<= n ;i++){
            if(arr[i]>1){
 
                if(arr[i]<min1){
                    min1=arr[i];
                    idx1=i;
                }
                else if(arr[i]<min2){
                    min2=arr[i];
                    idx2=i;
                }
            }
        }
 
        _1.push_back(idx1);
        arr[idx1]=1;
 
        if(cnt_1==0){
        _1.push_back(idx2);
        arr[idx2]=1;
        }
      }
 
    for(int i=1 ; i<=n ; i++)
        if(arr[i]>=2) _2.push_back(i);
 
    for(int i=0 ; i<_2.size()-1 ; i++){
        printf("%d %d\n",_2[i],_2[i+1]);
        arr[_2[i]]--; arr[_2[i+1]]--;
    }
 
    printf("%d %d\n",_1.back(),_2[0]);
    _1.pop_back();
    printf("%d %d\n",_1.back(),_2.back());
    _1.pop_back();
    arr[_2[0]]--,arr[_2.back()]--;
 
    for(int here:_1){
        for(int here2:_2){
            if(arr[here2]){
                printf("%d %d\n",here,here2);
                arr[here2]--;
                break;
            }
        }
    }
 
    return 0;
}