HDU-5813-Elegant Construction【多校2016】【贪心】

发布时间：2020-12-13 21:15:01 所属栏目：PHP教程来源：网络整理

导读：5813-Elegant Construction Problem Description Being an ACMer requires knowledge in many fields,because problems in this contest may use physics,biology,and even musicology as background. And now in this problem,you are being a city archite

5813-Elegant Construction

Problem Description
Being an ACMer requires knowledge in many fields,because problems in this contest may use physics,biology,and even musicology as background. And now in this problem,you are being a city architect!
A city with N towns (numbered 1 through N) is under construction. You,the architect,are being responsible for designing how these towns are connected by one-way roads. Each road connects two towns,and passengers can travel through in one direction.

For business purpose,the connectivity between towns has some requirements. You are given N non-negative integers a1 .. aN. For 1 <= i <= N,passenger start from town i,should be able to reach exactly ai towns (directly or indirectly,not include i itself). To prevent confusion on the trip,every road should be different,and cycles (one can travel through several roads and back to the starting point) should not exist.

Your task is constructing such a city. Now it’s your showtime!

Input
The first line is an integer T (T <= 10),indicating the number of test case. Each test case begins with an integer N (1 <= N <= 1000),indicating the number of towns. Then N numbers in a line,the ith number ai (0 <= ai < N) has been described above.

Output
For each test case,output “Case #X: Y” in a line (without quotes),where X is the case number starting from 1,and Y is “Yes” if you can construct successfully or “No” if it’s impossible to reach the requirements.

If Y is “Yes”,output an integer M in a line,indicating the number of roads. Then M lines follow,each line contains two integers u and v (1 <= u,v <= N),separated with one single space,indicating a road direct from town u to town v. If there are multiple possible solutions,print any of them.

Sample Input
3
3
2 1 0
2
1 1
4
3 1 1 0

Sample Output
Case #1: Yes
2
1 2
2 3
Case #2: No
Case #3: Yes
4
1 2
1 3
2 4
3 4

题目链接：HDU⑸813

题目大意：给出n个点（1~n），和每一个点能到达的点的个数（直接或间接）。问是不是存在这类可能性

题目思路：贪心，先给点的出度排序。

eg : 0 1 2 3
比如3这个点出度为2：先连1，再连2.如果不能连了则这是不可能存在的出度值。（每一个点只能向前面的点连，由于不存在回路）

以下是代码：

#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <list>

using  namespace std;
struct node
{
    int a,pos;
}p[2005];
bool cmp(node a,node b)
{
    return a.a < b.a;
}
vector <pair<int,int> > ans;
int n;
int solve()
{
    for (int i = 1; i <= n; i++)
    {
        int num = p[i].a;
        for (int j = 1; j < i; j++)
        {
            if (p[i].a == p[j].a) break;
            num--;
        }
        if (num > 0) return 0;
    }
    return 1;
}
int main()
{
    int t;
    cin >> t;
    int cas = 1;
    while(t--)
    {
        cin >> n;
        ans.clear();
        for (int i = 1; i <= n; i++)
        {
            cin >> p[i].a;
            p[i].pos = i;
        }
        sort(p + 1,p + n + 1,cmp);
        int flag = solve();
        if (!flag)
        {
            printf("Case #%d: Non",cas++);
            continue;
        }
        for (int i = 1; i <= n; i++)
        {
            int num = p[i].a;
            for (int j = 1; j < i; j++)
            {
                if (p[i].a == p[j].a) break;
                if (num <= 0) break;
                num--;
                ans.push_back(make_pair(p[i].pos,p[j].pos));
            }
        }
        int len = ans.size();
        printf("Case #%d: Yesn",cas++);
        printf("%dn",len);  //如果len等于0，这个0输出不输出都可以
        for (int i = 0; i < len; i++)
        {
            printf("%d %dn",ans[i].first,ans[i].second);
        }
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!