题解 | #小红的二分图构造#

E 小红的二分图构造

先思考如何把 判掉。

• 由于一条边贡献 的度，所以所有点的度数和必须为偶数。

接下来考虑如何构造。我们可以直接按照二分图的定义来，把原来的所有点分成两个集合，保证两个集合的度数和相等即可。

那么现在问题就变成了如何分集合，注意到这是一个经典01背包，但是需要知道具体的方案，所以需要进行转移的记录。

时间复杂度

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int INF = 0x3f3f3f3f;
int d[N];
int dp[N][N * N]; 
// dp[i][j] 表示前i个点中，A集合的度数和为j，A集合中的点数

int main() {
    int n; cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i ++ ) {
        cin >> d[i];
        sum += d[i];
    }
    if (sum & 1) {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 0; i <= n; i ++ ) {
        for (int j = 0; j <= sum / 2; j ++ ) dp[i][j] = -INF;
    }
    dp[0][0] = 0;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 0; j <= sum / 2; j ++ ) {
            // 不选i
            dp[i][j] = dp[i - 1][j];
            // 选i
            if (j >= d[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - d[i]] + 1);
        }        
    }
    if (dp[n][sum / 2] <= 0) {
        cout << -1 << endl;
        return 0;
    }
    // 分组
    int ni = n, nj = sum / 2;
    vector<int> v1, v2;
    while (ni > 0) {
        if (dp[ni][nj] == dp[ni - 1][nj]) {
            // 没选i，分到2组
            v2.push_back(ni);
            ni --;
        } else {
            // 选了i，分到1组
            v1.push_back(ni);
            nj -= d[ni];
            ni --;
        }
    }
    cout << sum / 2 << endl;
    int n1 = v1.size();
    int n2 = v2.size();
    for (int i = 0, j = 0; i < n1 && j < n2;) {
        cout << v1[i] << ' ' << v2[j] << endl;
        d[v1[i]] --, d[v2[j]] --;
        if (d[v1[i]] == 0) i ++;
        if (d[v2[j]] == 0) j ++;
    }
    return 0;
}