Codeforces Round 237 (Div. 2) - C. Restore Graph

Solost

2023 年 04 月 25 日

249 次浏览

暂无评论

1189字数

题目题解

## 题目链接

[链接](https://codeforces.com/problemset/problem/404/C)

## 题目大意

有n个房子，每个房子到其他房子最多有k条路，给你给出一栋房子到其他房子的最短距离，让你构造一个图，问你这张图构造出来是什么样的，输出a,b即a-b边长为1的路及有多少条这样的边.

## 题解

刚开始想的是dfs深搜,但是不知道为啥re7,然后换了一种写法。最后写的代码真的跟诗一样优雅。

* 先排序
* 然后双指针
  从当前点开始往后扫，扫到一个距离大于当前点1的点，然后加到第i个点里，然后不要超过这个点的度。刚开始的点即他自己家，出度可以为k,其他由于他有且只有一个父节点，然后出度只能是k-1，判断一下即可。注意，他只有一个家，还有每个点除了家它必须被用掉。

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

int n, k, sum, ed;
pii a[N];
int cnt[N];
vector<pii> q[N];
void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
        a[i] = {x, i};
        ed = max(ed, x);
    }
    sort(a + 1, a + n + 1);
    if(!a[2].x){
        cout << "-1\n";
        return;
    }
    for (int i = 1, j = 1; i <= n && j <= n; i++) {
        while (j <= n && a[j].x == a[i].x) j++;
        for (int h = 1; h <= k - (i != 1) && j <= n; j++, h++) {
            if (a[j].x == a[i].x + 1) {
                sum++;
                cnt[a[j].x]--;
                q[a[i].y].push_back({a[i].y, a[j].y});
            }
            else break;
        }
    }
    for(int i = 1; i <= ed; i++){
        if(cnt[i]){
            cout << "-1\n";
            return;
        }
    }
    cout << sum << endl;
    for(int i = 0; i <= n; i++){
        for(auto [x, y] : q[i]){
            cout << x << " " << y << endl;
        }
    }
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 04 月 25 日