题解 | 小红的二分图构造

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 名词解释没做全
// 什么是节点的度不说清楚，看示例，大概是节点的边的数量
// 二分图大概是，所有V节点连接一个以上的U节点，线段可以独立
// 算法参考了网友，但是稍微做了一点修改
// 选出合适的左右队列后，直接填充生成的线段明显是错误的，两个点之间会出现多条线段，并且测试能够通过
// 这里尝试左序列升序，右序列降序，大致是对的，没有详细测试
bool Dfs(const vector<int>& d, int left, int i, vector<int>& l, vector<int>& r) {
    if(left == 0) {
        for(int j = i; j < (int)d.size(); j++) {
            r.push_back(j);
        }
        return true;
    }
    if(left < 0) {
        return false;
    }
    if(i == (int)d.size()) {
        return false;
    }
    l.push_back(i);
    if( Dfs(d, left - d[i], i+1, l, r) ) {
        return true;
    }
    l.pop_back();
    r.push_back(i);
    if( Dfs(d, left, i+1, l, r)) {
        return true;
    }
    r.pop_back();
    return false;
}
int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    int sum = 0;
    for(auto& v : d) {
        cin >> v;
        sum += v;
    }
    int l = n/2;
    int r = n-l;
    auto line = sum / 2;
    if(sum&1 || l*r < line || line < r) {
        cout << "-1" << endl;
        return 0;
    }
    vector<int> left, right;
    if(!Dfs(d, sum/2, 0, left, right)) {
        cout << "-1" << endl;
        return 0;
    }
    cout << sum/2 << endl;
    sort(left.begin(), left.end(), [&d](int& l, int& r) {
        return d[l] > d[r];
    });
    sort(right.begin(), right.end(), [&d](int& l, int& r) {
        return d[l] < d[r];
    });
    for(auto li : left) {
        int j = 0;
        for(auto k = 0; k < d[li];k++) {
            while(d[right[j]] == 0) {
                j++;
            }
            cout << li + 1 << " " << right[j] + 1 << endl;
            d[right[j]]--;
            j++;
            j %= right.size();
        }
    }
}
// 64 位输出请用 printf("%lld")