萌妹子刚学2-SAT救助QAQ

P4171 [JSOI2010] 满汉全席

NaCly_Fish @ 2019-02-10 21:23:07

莫名只有50分。。求找错
(应该不是清空数组的问题)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#define inf 0x3f3f3f3f
#define ll long long
#define N 203
#define reg register
using namespace std;

vector<int> adj[N];
int low[N],dfn[N],clr[N],stk[N];
bool vis[N];
int scc,size,cnt;

inline void read(int &x);
void print(int x);
bool solve();
void tarjan(int u);

int main(){
    int T;
    bool ans;
    read(T);
    while(T--){
        ans = solve();
        printf(ans?"GOOD\n":"BAD\n");
    }
    return 0;
}

bool solve(){
    string s1,s2;
    cnt = scc = size = 0;
    memset(clr,0,sizeof(clr));
    memset(dfn,0,sizeof(clr));
    memset(vis,0,sizeof(vis));
    memset(low,0,sizeof(low));
    memset(stk,0,sizeof(stk));
    int n,m,a,b,va,vb;
    read(n),read(m);
    for(int i=1;i<=(n<<1);++i)
        adj[i].clear();
    for(int i=1;i<=m;++i){
        cin>>s1>>s2;
        a = s1[1]-'0';
        va = s1[0]=='h'?1:0;
        b = s2[1]-'0';
        vb = s2[0]=='h'?1:0;
        adj[a+n*(va&1)].push_back(b+n*(vb^1));
        adj[b+n*(vb&1)].push_back(a+n*(va^1));
    }    
    for(int i=1;i<=(n<<1);++i){
        if(dfn[i]) continue;
        tarjan(i);
    }
    for(int i=1;i<=n;++i){
        if(clr[i]!=clr[i+n]) continue;
        return false;
    }
    return true;
}

void tarjan(int u){
    low[u] = dfn[u] = ++cnt;
    vis[u] = true;
    stk[++size] = u;
    int v,l = adj[u].size();
    for(int i=0;i<l;++i){
        v = adj[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }else if(vis[v])
            low[u] = min(low[u],dfn[v]);
    }
    if(low[u]!=dfn[u]) return;
    ++scc;
    do{
        vis[stk[size]] = false;
        clr[stk[size]] = scc;
        --size;
    }while(stk[size+1]!=u);
}

inline void read(int &x){
    x = 0;
    char c = getchar();
    while(c<'0'||c>'9') c = getchar();
    while(c>='0'&&c<='9'){
        x = (x<<3)+(x<<1)+(c^48);
        c = getchar();
    }
}

void print(int x){
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

by NaCly_Fish @ 2019-02-11 15:29:47

AC了。。
做带字符串题的时候一定要注意字符串的处理


by Makasukaka @ 2019-03-26 20:38:31

老faker牛爷爷


by mikechu @ 2020-05-23 15:07:10

考古


上一页 |