Cf Round 335 Div.1 B. Lazy Student

Posted on By 二价氢

#题目大意 给定若干的边权和这条边是否在最小生成树里的信息,要求复原出一个图,使其的最小生成树之一符合输入

#思路 将所有边按照边权排序,同时使得被选中的边尽量靠前 然后我们可以让最小生成树是一颗菊花树 答案不存在的情况就是,到排序后的第 条边的时候已经得到了一个 个节点的完全图,但得到的边是未被选中的 添加不在最小生成树上的边可以按照 这样的顺序 #Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100000 + 5;
const int maxm = 100000 + 5;
struct edge{
    int id, w, sel;
    int u, v;
}e[maxm];
int n, m;
int maxconn = 1;
int curru = 2, currv = 2;
int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        e[i].id = i;
        cin >> e[i].w >> e[i].sel;
    }
    sort(&e[0], &e[m],
            [](const edge &a, const edge &b)
            {return a.w < b.w || (a.w == b.w && a.sel > b.sel);});
    for (int i = 0; i < m; i++)
    {
        if (e[i].sel)
        {
            maxconn++;
            e[i].u = maxconn;
            e[i].v = 1;
        } else {
            if (curru == currv)
            {
                currv ++;
                curru = 2;
            }
            if (currv > maxconn) {cout << "-1\n";return 0;}
            e[i].u = currv;
            e[i].v = curru;
            curru++;
        }
    }
    sort(&e[0], &e[m],
            [](const edge &a, const edge &b)
            {return a.id < b.id;});
    for (int i = 0; i < m; i++)
        cout << e[i].u << " " << e[i].v << "\n";
    return 0;
}