UVA - 11659 Informant

Intuition

Since the total informant can only be up to 20, we can use an integer to represent if it’s reliable by :

reliable table
00001 : A is reliable
00010 : B is reliable
00110 : B and C is reliable
...etc.

So as the unreliables.

Brute force : pull out every possibilities

Since we discover that n informant has to represent with n bits, the full range of the possibles is $0$ ~ $2^n-1$ with it represented in int.

And per possibilities, we have to verify it with every informant that is reliable to tell if it’s a valid possible reliable informants allocation.

Therefore, we can calculate a time complexity of:
$$O(2^N*N)$$
Where $N$ is the number of informants. Since $N$ has maximum value of 20, it cost at most $2^{20}*20 \sim {2}*10^7$, which will not TLE at most judge.

Sample Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int nums[21], fnums[21];
    int n, m;
    while (cin >> n >> m && n)
    {
        // reset
        memset(nums, 0, sizeof(nums));
        memset(fnums, 0, sizeof(fnums));
        // handle input
        int x, y;
        for (int i = 0; i < m; i++)
        {
            cin >> x >> y;
            if (y > 0)
                nums[x - 1] |= 1 << y - 1;
            else
                fnums[x - 1] |= 1 << -y - 1;
        }
        // solve
        int hightest = (1 << n), res = 0;
        for (int i = 0; i < hightest; i++)
        {
            int now = __builtin_popcount(i), ni = (~i);
            if (res >= now)
                continue;
            bool flag = true;
            for (int j = 0; j < n; j++)
                if ((i & (1 << j)) && ((fnums[j] & ni) != fnums[j] || (nums[j] & i) != nums[j]))
                {
                    flag = false;
                    break;
                }
            if (flag)
                res = now;
        }
        cout << res << endl;
    }
}