2016多校7 HDU 5813 Elegant Construction

2016多校聯合訓練#7

HDU 5813 Elegant Construction

水題

傳送門：HDU

題意

圖上有n個點，點之間有單向的路，告訴你每個點能到達的點的個數，讓你建構一個圖出來。建議讀原題。

思路

排序，按到達點數量從小到大排，然後正向讀點，每到一個點，往前連路，建圖就行了。

代碼

#include <stdio.h>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <math.h>
#include <stack>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef long long ll;

const int MAXN=;
const double eps=;
const int oo=;
struct ppp{
    int a,b;
    ppp (){};
    ppp (int _first,int _second)
    {
        a=_first;
        b=_second;
    }
    bool operator <(const ppp &c) const
    {
        return a<c.a;
    }
};
typedef struct ppp P;
int main()
{
    int T;
    scanf("%d",&T);
    for(int t=;t<=T;t++)
    {
        int n;
        scanf("%d",&n);
        P num[MAXN];
        for(int i=;i<n;i++)
        {
            int temp;
            scanf("%d",&temp);
            num[i]=P(temp,i+);
        }
        sort(num,num+n);
        printf("Case #%d: ",t);
        bool flag=false;
        for(int i=;i<n;i++)
        {
            if(num[i].a>i)
            {
                printf("No\n");
                flag=true;
                break;
            }
        }
        if(flag) continue;
        printf("Yes\n");
        vector<P> vec;
        for(int i=;i<n;i++)
        {
            int cnt=;
            for(int j=;j<i;j++)
            {
                if(cnt==num[i].a) break;
                cnt++;
                vec.push_back(P(num[i].b,num[j].b));

            }
        }
        printf("%d\n",vec.size());
        for(int i=;i<vec.size();i++)
        {
            printf("%d %d\n",vec[i].a,vec[i].b);
        }
    }
}