Wedding

C++(g++ 7.5.0) 解法, 执行用时: 2ms, 内存消耗: 480K, 提交时间: 2023-01-16 12:54:15

#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#define maxn 100
using namespace std;
int n,m;
int fir[maxn],nxt[maxn*maxn],to[maxn*maxn],tot;
bool flag;
void read(int &a,bool &b)
{
    char c;a=0;
    while(!isdigit(c=getchar()));
    while(isdigit(c)) a=a*10+c-'0',c=getchar();
    b=(c=='w');
}
void line(int x,int y)
{
    nxt[++tot]=fir[x];
    fir[x]=tot;
    to[tot]=y;
}
void add(int u,bool x,int v,bool y)
{
    u=u*2+x,v=v*2+y;
    line(u,v^1);
    line(v,u^1);
}
int dfn[maxn],low[maxn],stk[maxn],tp,scc[maxn],scnt,tim;
void tarjan(int u)
{
    dfn[u]=low[u]=++tim;
    stk[++tp]=u;
    for(int i=fir[u];i;i=nxt[i])
        if(!dfn[to[i]]) tarjan(to[i]),low[u]=min(low[u],low[to[i]]);
        else if(!scc[to[i]]) low[u]=min(low[u],dfn[to[i]]);
    if(dfn[u]==low[u])
    {
        ++scnt;
        do
        {
            if(scc[stk[tp]^1]==scnt) flag=1;
            scc[stk[tp]]=scnt;
        }while(stk[tp--]!=u);
    }
}
int Q[maxn],in[maxn],cf[maxn];
vector<int>e[maxn];
bool mark[maxn];
void Topsort()
{
    int h=1,t=0,u;
    for(int i=1;i<=scnt;i++)
        if(!in[i]) Q[++t]=i;
    while(h<=t)
    {
        u=Q[h++];
        if(!mark[cf[u]]) mark[u]=1;
        for(int i=e[u].size()-1;i>=0;i--)
            if((--in[e[u][i]])==0) Q[++t]=e[u][i];
    }
}
void init()
{
    tim=scnt=tot=flag=tp=0;
    memset(in,0,sizeof in);
    memset(cf,0,sizeof cf);
    memset(fir,0,sizeof fir);
    memset(dfn,0,sizeof dfn);
    memset(scc,0,sizeof scc);
    memset(mark,0,sizeof mark);
    for(int i=1;i<=2*n;i++) e[i].clear();
}
int main()
{
    int x,y;
    bool u,v;
    while(scanf("%d%d",&n,&m),n)
    {
        init();
        line(1,0);
        for(int i=1;i<=m;i++)
        {
            read(x,u);
            read(y,v);
            add(x,u,y,v);
        }
        n*=2;
        for(int i=0;i<n&&!flag;i++)
            if(!dfn[i]) tarjan(i);
        if(flag) {puts("bad luck");continue;}
        for(int u=0;u<n;u++)
            for(int i=fir[u];i;i=nxt[i])
                if(scc[u]!=scc[to[i]]) e[scc[to[i]]].push_back(scc[u]),in[scc[u]]++;
        for(int i=0;i<n;i++)
            cf[scc[i]]=scc[i^1];
        Topsort();
        for(int i=2;i<n;i+=2)
        {
            if(i>2) putchar(' ');
            if(mark[scc[i]]) printf("%dw",i/2);
            else printf("%dh",i/2);
        }
        putchar('\n');
    }
}

C++ 解法, 执行用时: 4ms, 内存消耗: 848K, 提交时间: 2021-08-04 11:34:23

#include<bits/stdc++.h>
#define PI acos(-1.0)
#define E 1e-6
#define MOD 16007
#define INF 0x3f3f3f3f
#define N 10001
#define LL long long
using namespace std;
bool vis[N*2];
int Stack[N*2],top;
vector<int> G[N*2];
void init(int n){
    memset(vis,false,sizeof(vis));
    for(int i=0;i<2*n;i++)
        G[i].clear();
}
void addOrClause(int x,int xVal,int y,int yVal){
    x=x*2+xVal;
    y=y*2+yVal;
    G[x^1].push_back(y);
    G[y^1].push_back(x);
}
void addAndClause(int x,int xval,int y,int yval) {
    x=x*2+xval;
    y=y*2+yval;
    G[x].push_back(y);
}
bool dfs(int x){
    if(vis[x^1])
        return false;
 
    if(vis[x])
        return true;
    vis[x]=true;
 
    Stack[top++]=x;
 
    for(int i=0;i<G[x].size();i++)
        if(!dfs(G[x][i]))
            return false;
 
    return true;
}
bool twoSAT(int n){
    for(int i=0;i<2*n;i+=2){
        if(!vis[i] && !vis[i+1]){
            top=0;
 
            if(!dfs(i)){
                while(top>0)
                    vis[Stack[--top]]=false;
 
                if(!dfs(i+1))
                    return false;
            }
        }
    }
    return true;
}
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF&&(n+m)){
 
        init(n*2);
 
        addAndClause(0,1,0,0);//新娘在左
        addAndClause(1,0,1,1);//新郎在右
 
        //n-1对夫妇
        for(int i=1;i<n;i++){
            //拆点
            int a=i*2;//妻子
            int b=i*2+1;//丈夫
 
            //初始条件
            addAndClause(a,0,b,1);
            addAndClause(a,1,b,0);
            addAndClause(b,0,a,1);
            addAndClause(b,1,a,0);
        }
 
        for(int i=0;i<m;i++){
            int a,b;//有奸情的两个人
            char ch1[10],ch2[10];
 
            scanf("%d%s%d%s",&a,ch1,&b,ch2);
 
            //拆点
            if(ch1[0]=='w')
                a=a*2;//妻子
            else
                a=a*2+1;//丈夫
            if(ch2[0]=='w')
                b=b*2;//妻子
            else
                b=b*2+1;//丈夫
 
            //添加限制条件
            addAndClause(a,1,b,0);
            addAndClause(b,1,a,0);
        }
 
        if(!twoSAT(n*2))
            printf("bad luck\n");
        else{
            for(int i=2;i<2*n;i+=2){
                if(vis[i*2])
                    printf("%dw ",i/2);
                if(vis[(i+1)*2])
                    printf("%dh ",i/2);
            }
            printf("\n");
        }
    }
 
    return 0;
}

详情