UVa 12035 - War Map

contents

1. 1. Problem
2. 2. Sample Input
3. 3. Sample Output
4. 4. Solution

Problem

給每個節點的度 (degree)，是否能構成二分圖？

Sample Input

4
4
3 1 3 3
5
1 2 1 1 3
4
2 3 2 3
7
4 1 2 3 1 2 3

Sample Output

Case 1: NO
Case 2: YES
Case 3: NO
Case 4: YES

Solution

劃分成兩個集合，則兩邊的 degree 總和一定會相同，因此得到了基礎的窮舉概念。

然後對於窮舉的時候，左集合的元素最大值一定要小於等於右集合大小，反之亦然。
// s 和 t 集合, max(s[i]) <= |t|

這樣窮舉只能保證基礎的條件，而事實上採用 greedy 的驗證方式，從最大度的點開始分配連線給最大度的點，如果最後能分配完成即可找到一種二分圖的解。當然，有人嘗試了 maxflow 的驗證方式也是相當靠譜，不過速度會慢了些，而且還不是很容易 coding。

而這樣的解法仍然會拉 TLE 的緊抱，因此考慮將相同 degree 的窮舉方式壓縮，例如說有 3 個 2 需要窮舉，而採用兩個集合劃分的方式 (0, 3) (1, 2) (2, 1) (3, 0) 四種方式 …，從 2^3 = 8 降到 4 次，速度會快快快很多。

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

int n, m, A[32], B[32], totdeg;
pair<int, int> C[32];
int Ldeg[32], Rdeg[32];

int checkBipartite(int Ldeg[], int L, int Rdeg[], int R) {
    priority_queue<int> pQ;
    int x, cc = 0;
    for (int i = 0; i < R; i++)
        pQ.push(Rdeg[i]);
    for (int i = 0; i < L; i++)
        B[cc++] = Ldeg[i];
    sort(B, B+L, greater<int>());
    for (int i = 0; i < L; i++) {
        queue<int> Q;
        while (B[i] && !pQ.empty()) {
            B[i]--;
            x = pQ.top(), pQ.pop();
            x--;
            if (x)
                Q.push(x);
        }
        if (B[i])
            return 0;
        while (!Q.empty())
            pQ.push(Q.front()), Q.pop();
    }
    return pQ.empty();
}
int dfs(int idx, int lsize, int rsize, int ldeg, int rdeg, int lneed, int rneed) {
    if (ldeg > totdeg/2 || rdeg > totdeg/2)
        return 0;
    if (lneed + rneed > n || lsize + n - idx < lneed || rsize + n - idx < rneed)
        return 0;
    if (idx == m)
        return lsize >= lneed && rsize >= rneed && checkBipartite(Ldeg, lsize, Rdeg, rsize);
    for (int i = idx == 0; i <= C[idx].second; i++) {
        int l = i, r = C[idx].second - i, ln = lneed, rn = rneed;
        for (int j = 0; j < l; j++)
            Ldeg[lsize+j] = C[idx].first, rn = max(rn, C[idx].first);
        for (int j = 0; j < r; j++)
            Rdeg[rsize+j] = C[idx].first, ln = max(ln, C[idx].first);
        if (dfs(idx+1, lsize+l, rsize+r, ldeg+C[idx].first*l, rdeg+C[idx].first*r, ln, rn)) {
            return 1;
        }
    }
    return 0;
}

int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        totdeg = 0;
        for (int i = 0; i < n; i++)
            totdeg += A[i];
        sort(A, A+n, greater<int>());
        m = 0;
        C[m] = make_pair(A[0], 1), m++;
        for (int i = 1; i < n; i++) {
            if (A[i] == C[m-1].first)
                C[m-1].second++;
            else
                C[m] = make_pair(A[i], 1), m++;
        }
        int flag = totdeg%2 == 0 && dfs(0, 0, 0, 0, 0, 0, 0);
        printf("Case %d: %s\n", ++cases, flag ? "YES" : "NO");
    }
    return 0;
}

接近 TLE 的版本，概率通過得 AC。

#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

int n, A[32], B[32], totdeg;
int Ldeg[32], Rdeg[32];

int checkBipartite(int Ldeg[], int L, int Rdeg[], int R) {
    priority_queue<int> pQ;
    int x, cc = 0;
    for (int i = 0; i < R; i++)
        pQ.push(Rdeg[i]);
    for (int i = 0; i < L; i++)
        B[cc++] = Ldeg[i];
    sort(B, B+L, greater<int>());
    for (int i = 0; i < L; i++) {
        queue<int> Q;
        while (B[i] && !pQ.empty()) {
            B[i]--;
            x = pQ.top(), pQ.pop();
            x--;
            if (x)
                Q.push(x);
        }
        if (B[i])
            return 0;
        while (!Q.empty())
            pQ.push(Q.front()), Q.pop();
    }
    return pQ.empty();
}
int dfs(int idx, int lsize, int rsize, int ldeg, int rdeg, int lneed, int rneed) {
    if (ldeg > totdeg/2 || rdeg > totdeg/2)
        return 0;
    if (lneed + rneed > n || lsize + n - idx < lneed || rsize + n - idx < rneed)
        return 0;
    if (idx == n)
        return lsize >= lneed && rsize >= rneed && checkBipartite(Ldeg, lsize, Rdeg, rsize);
    Ldeg[lsize] = A[idx];
    if (dfs(idx+1, lsize+1, rsize, ldeg+A[idx], rdeg, lneed, max(rneed, A[idx])))
        return 1;
    Rdeg[rsize] = A[idx];
    
    if (idx > 0) {
    if (dfs(idx+1, lsize, rsize+1, ldeg, rdeg+A[idx], max(lneed, A[idx]), rneed))
        return 1;
    }
    return 0;
}

int main() {
    int testcase, cases = 0;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        totdeg = 0;
        for (int i = 0; i < n; i++)
            totdeg += A[i];
        sort(A, A+n);
        int flag = totdeg%2 == 0 && dfs(0, 0, 0, 0, 0, 0, 0);
        printf("Case %d: %s\n", ++cases, flag ? "YES" : "NO");
    }
    return 0;
}

/*
 10000
 6
 3 0 2 2 3 0
 12
 0 0 0 0 0 0 0 0 0 0 0 0
 20
 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19
 4
 3 1 3 3
 5
 1 2 1 1 3
 4
 2 3 2 3
 7
 4 1 2 3 1 2 3
 */