Uva11659 Informants

題目大意

題目會給與好幾個informant
informant 內的資訊是這個 informant 信任或不信任哪些 informant
我們要找出最多個同時被信任又不會衝突的 informant

重點觀念

分析

• 將 informant 存為 reliable 跟 unreliable 兩個數值(二進位)
• 窮舉所有可能的解，若解的信賴數量小於最大值則跳過
• 確定此解所信賴的線人所提供的資訊都為正確的 (解所信任與不信任的人要與此線人相同)

程式題目碼

#include <string.h>

#include <algorithm>
#include <iostream>

using namespace std;

int countBit(int i) {
    int count = 0;
    while (i) {
        if (i & 1) {
            count++;
        }
        i >>= 1;
    }
    return count;
}

int main() {
    int n, a;

    while (cin >> n >> a) {
        if (a == 0 && n == 0) {
            break;
        }
        int saysCorrect[n], saysWrong[n];
        memset(saysCorrect, 0, sizeof(saysCorrect));
        memset(saysWrong, 0, sizeof(saysWrong));

        for (int index = 0; index < a; index++) {
            int x, y;
            cin >> x >> y;

            if (y > 0) {
                saysCorrect[x - 1] |= (1 << y - 1);
            } else {
                saysWrong[x - 1] |= (1 << -y - 1);
            }
        }

        int highest = (1 << n) - 1;
        int maxPositive = 0;

        for (int i = 1; i <= highest; i++) {
            int unreliable = (~i) & highest;
            int reliableNum = countBit(i);
            if (reliableNum < maxPositive) {
                continue;
            }

            bool flag = true;

            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) && (((unreliable & saysWrong[j]) != saysWrong[j]) || ((i & saysCorrect[j]) != saysCorrect[j]))) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                maxPositive = reliableNum;
            }
        }

        cout << maxPositive << endl;
    }

    return 0;
}