Real liar and search Collection + dp + backtracking

There are two kinds of inhabitants on an island, one is God and the other is devil.

Gods will never tell lies, and demons will never tell the truth.

Each member on the island has an integer number (similar to the ID number to distinguish each member).

Now you have nn opportunities to ask questions, but the content of the question can only be to ask one resident whether the other resident is a God. Please judge the identity of each resident according to the collected answers.

Input format

The input contains multiple sets of test cases.

The first line of each test case contains three non negative integers n, P1, p2n, P1 and P2, where nn is the total number of times you can ask questions, p1p1 is the total number of gods and p2p2 is the total number of demons.

The next nn line contains two integers xi,yixi,yi and a string aiai, where xi,yixi,yi is the number of the residents on the island. You will ask the residents with number xixi whether the residents with number yiyi are gods,

aiai is his answer. If aiai is yes, it means he answers you "yes". If aiai is no, it means he answers you "no".

xi,yixi,yi may be the same, which means that you are asking whether the person himself is a God.

When the input is 0 occupying one line, it indicates that the input is terminated.

Output format

For each group of test cases, if the information obtained from the inquiry is enough to enable you to judge the identity of each resident, output the numbers of all gods in one line. After the output, output end in another line, indicating that the output of the use case is over.

If the information obtained is not enough to judge the identity of each resident, output no, and the output also occupies one line.

Data range

1≤xi,yi≤p1+p21≤xi,yi≤p1+p2,
0≤n<1000,0≤p1,p2<3000≤n<1000,0≤p1,p2<300

Input sample:

2 1 1
1 2 no
2 1 no
3 2 1
1 1 yes
2 2 yes
3 3 yes
2 2 1
1 2 yes
2 3 no
5 4 3
1 2 yes
1 3 no
4 5 yes
5 6 yes
6 7 no
0 0 0

Output example:

no
no
1
2
end
3
4
5
6
end

analysis

There are only four situations for inquiry
God yes
God demon no
Demon God no
Demon yes
That is, two people of the same kind are yes and the other is no. The weighted union query set is used to maintain the relationship between everyone. The root node of each set is marked as 0, the value of the same kind of child node and parent node is 0, and the value of the different kind of child node and parent node is 1. For the following relationships, 1, 3 and 6 are of the same kind, and 2, 4 and 5 are of another kind.
Using the weighted parallel query set storage relationship, f[i]=j indicates that the parent node of I is j, d[i] = 1 indicates that it is different from the parent node, and d[i] = 0 indicates that it is the same as the parent node

Path compression: for node 6 directly connected to node 1 after compression, update f[6] = 1, d[6] = d[6] ^ d[4] = 0

Merge: x and Y same kind op=0, x and y different kind op=1
f[fy] = fx ; d[fy] = d[y] ^ d[x] ^ op

For data 4
5 4 3
1 2 yes
1 3 no
4 5 yes
5 6 yes
6 7 no
Set 1, 2 are of the same kind and 3 are of another kind
Set 2 4 5 6 is of the same kind and 7 is of another kind
Each set has two situations. For set 1, 1 and 2 may be gods, 3 demons, or 1, 2 demons, and 3 gods.
Dynamic programming counts the number of (p, q) this situation. If it is 1, everyone's identity can be determined.

The identity of each person can be determined by backtracking to determine the identity of each set root node
For example: dp(4,3)=1. Set 2 is selected last time. The previous state can only be dp(1,2) and dp(3,1). dp(3,1)=0 and dp(1,2)=1. It means that 4,5,6 in set 2 are gods and 7 are demons

Reference code

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

const int N = 310;

int n, p, q, x, y;
int f[2*N], d[2*N], dp[N][N], a[2*N][2], val[2*N];
string str;
bool op;

int find(int x){//Parallel search set with path compression
    if(x!=f[x]){
        int u = find(f[x]);
        d[x] ^= d[f[x]];
        f[x] = u;
    }
    return f[x];
}

void print(int x, int y, int top){//to flash back
    if(x==0 && y==0) return;
    while(top && !a[top][0] && !a[top][1]) top--;
    int i = a[top][0], j = a[top][1];
    if(x-j>=0 && y-i>=0 && dp[x-j][y-i]==1) {
        val[top] = 0;
        print(x-j, y-i, top-1);
    }
    else if(x-i>=0 && y-j>=0 && dp[x-i][y-j]==1){
        val[top] = 1;
        print(x-i, y-j, top-1);
    }
}

int main(){
    while(cin >> n >> p >> q){
        if(n==0 && p==0 && q==0) break;
        for(int i=0; i<=p+q; i++){
            f[i] = i;
            d[i] = 0;
        } 
        while(n--){//Read in data and merge sets
            cin >> x >> y >> str;
            if(str=="yes") op = 0;
            else op = 1;
            int fx = find(x), fy = find(y);
            if(fx!=fy){
                f[fy] = fx;
                d[fy] = d[x]^d[y]^op;
            }
      
        }
        memset(val, 0, sizeof val);
        memset(dp, 0, sizeof dp);
        memset(a, 0, sizeof a);
        for(int i=1; i<=p+q; i++){//Count the number of gods and demons in each collection
            x = find(i);
            a[x][d[i]]++;
        }
        int cnt = 0;
        dp[0][0] = 1;
        for(int i=1; i<=p+q; i++){//Calculate dp(i, j), the possible number of i born and j demons
            if(a[i][0] || a[i][1]){
                cnt += a[i][0] + a[i][1];
                for(int j=p, k; j>=0; j--){
                    k = cnt - j;
                    if(k<0) continue;
                    if(j-a[i][0]>=0 && k-a[i][1]>=0){
                        dp[j][k] += dp[j-a[i][0]][k-a[i][1]];

                    }
                    if(j-a[i][1]>=0 && k-a[i][0]>=0)
                        dp[j][k] += dp[j-a[i][1]][k-a[i][0]];   
                }    
            }
        }
        if(dp[p][q]==1) {//dp(p, q) has only one case, which can determine everyone's identity
            int cnt = 0;
            for(int i=1; i<=p+q; i++) cnt += d[i];
            if(cnt == p) op = 1;
            else op = 0;
            print(p, q, p+q);
            for(int i=1; i<=p+q; i++){
                int u = find(i);
                if(val[u]^d[i]) 
                    cout << i << endl;
            }
            cout << "end" << endl;
        }
        else cout << "no" << endl;
    }
    return 0;
}

Tags: C++ dp

Posted by jOE :D on Fri, 20 May 2022 23:35:55 +0300