p1121.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
#include <bitset>
using namespace std;
const int MAXN = 52;
int main(){
    bool a[MAXN][MAXN];
    bitset <26> b[MAXN];
    bitset <26> c[MAXN];
    string s;
    int n;
    memset(a,0,sizeof(a));
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> s;
        if(s != ".")
            for(int j = 0;j < s.size();++j) b[i][s[j]-'A'] = 1;
        cin >> s;
        c[i].set();
        if(s != ".")
            for(int j = 0;j < s.size();++j) c[i][s[j]-'A'] = 0;
    }
    int x,y;
    while(cin >> x >> y && (x || y)) a[x][y] = 1;
    bitset <26> ans[MAXN];
    for(int i = 1;i <= n;++i) ans[i] = b[i];
    for(int i = 1;i <= n;++i){
        int l[1000];
        int f(0),ch(0);
        l[0] = i;
        while(f <= ch){
            for(int j = 1;j <= n;++j)
                if(a[l[f]][j] && 
                ((ans[l[f]] | ans[j]) & c[j]) != ans[j]){
                    l[++ch] = j;
                    ans[j] = (ans[l[f]] | ans[j]) & c[j];
                }
            ++f;
        }
    }
    for(int i = 1;i <= n;++i){
        putchar(':');
        for(int j = 0;j < 26;++j)
            if(ans[i][j]) printf("%c",j+'A');
        puts(":");
    }
}