萌新の智障错误(40分)

P4171 [JSOI2010] 满汉全席

Augury @ 2023-01-31 10:25:40

码风奇怪,请不要嫌弃

#include<bits/stdc++.h>
#define f(x) (x=='h')
using namespace std;
const int maxn=210;
int n,m;
int dfn[maxn],low[maxn],col[maxn];
bool vis[maxn];
stack<int>st;
int cnt=0,clr=0;
vector<int>g[maxn];
void tarjan(int now){
    dfn[now]=low[now]=++cnt;
    vis[now]=1;
    st.push(now);
    for(int i=0;i<(int)g[now].size();i++){
        int nxt=g[now][i];
        if(!dfn[nxt]){
            tarjan(nxt);
            low[now]=min(low[now],low[nxt]);
        }
        else if(vis[nxt])low[now]=min(low[now],dfn[nxt]);
    }
    if(dfn[now]==low[now]){
        clr++;
        int tmp=-1;
        while(tmp!=now){
            tmp=st.top();
            st.pop();
            col[tmp]=clr;
            vis[tmp]=1;
        }
    }
}
void init(){
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(col,0,sizeof(col));
    for(int i=1;i<=n<<1;i++)g[i].clear();
    cnt=clr=0;
}
void real_main(){
    scanf("%d%d",&n,&m);
    init();
    for(int i=1;i<=m;i++){
        char a,c;
        int b,d;
        cin>>a>>b>>c>>d;
        g[b+(!f(a))*n].push_back(d+f(c)*n);
        g[d+(!f(c))*n].push_back(b+f(a)*n);
    }
    for(int i=1;i<=n<<1;i++)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;i++){
        if(col[i]==col[i+n]){
            cout<<"BAD\n";
            return;
        }
    }
    cout<<"GOOD\n";
    return;
}
int main(){
    int K;
    scanf("%d",&K);
    while(K--)real_main();
}

再上面的 tarjan 中,节点出栈后应该将 vis[now]=0 ,然鹅蒟蒻写成了 vis[now]=1100\rightarrow 40


|