题解 | 小红的二分图构造

#include <iostream>
#include <vector>
using namespace std;

bool dfs(const int& first, const int& sum, const int& target, const int& n, const vector<int>& d, vector<int>& v1, vector<int>& v2){
    if(sum == target){
        if(first != n){
            for(int i=first; i<n; ++i){
                v2.emplace_back(i+1);
            }
        }
        return true;
    }else if(sum > target){
        return false;
    }
    for(int i=first; i<n; ++i){
        v1.emplace_back(i+1);
        if(dfs(i+1, sum+d[i], target, n, d, v1, v2)){
            return true;
        }else{
            v1.pop_back();
            v2.emplace_back(i+1);
            if (dfs(i + 1, sum, target, n, d, v1, v2)) {
                return true;
            }
            v2.pop_back();
            return false;
        }
    }
    
    return false;
}

int main() {
    int n;
    cin >> n;
    vector<int> d(n);
    int sum = 0;
    for(int i=0; i<n; ++i){
        cin >> d[i];
        sum += d[i];
    }
    if(sum%2==1){
        cout << -1 << endl;
        return 0;
    }
    vector<int> v1, v2;
    if(!dfs(0, 0, sum/2, n, d, v1, v2)){
        cout << -1 << endl;
        return 0;
    }
    cout << sum/2 << endl;
    int i = 0, j = 0;
    int n1 = v1.size();
    int n2 = v2.size();
    while(i < n1 && j < n2){
        cout << v1[i] << ' ' << v2[j] << endl;
        d[v1[i]-1] --, d[v2[j]-1] --;
        if (d[v1[i]-1] == 0) i ++;
        if (d[v2[j]-1] == 0) j ++;
    }

    return 0;
}
// 64 位输出请用 printf("%lld")