poj3648

poj3648

题意

有一对新人结婚,n-1对夫妇去参加婚礼.有一个很长的座子,新娘与新郎坐在座子的两边(相反).接下来n-1对夫妇就坐,其中任何一对夫妇都不能坐在同一边,且(有一些人有奸情)这些有奸情的两个人不能同时坐在新娘对面.(只能分开做,或者都坐到新娘一边去)。对于每个输入实例，输出应该坐在新娘同一边的人编号。

分析

弄清楚题意后，建图比较简单（对立关系比较单一），注意新娘连边到新郎，保证新郎一定在对面，且新郎也可能有奸情。

code

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

const int INF = 1e9;

const int MAXN = 2e4 + 5;

int vis[MAXN], flag[MAXN];

vector<int> G[MAXN], rG[MAXN];

vector<int> vs;

int n, m;

void addedge(int x, int y)

{

    G[x].push_back(y);

    rG[y].push_back(x);

}

void dfs(int u)

{

    vis[u] = 1;

    for(int i = 0; i < G[u].size(); i++)

    {

        int v = G[u][i];

        if(!vis[v]) dfs(v);

    }

    vs.push_back(u);

}

void rdfs(int u, int k)

{

    vis[u] = 1; flag[u] = k;

    for(int i = 0; i < rG[u].size(); i++)

    {

        int v = rG[u][i];

        if(!vis[v]) rdfs(v, k);

    }

}

int scc()

{

    vs.clear();

    memset(vis, 0, sizeof vis);

    for(int i = 0; i < n; i++)

        if(!vis[i]) dfs(i);

    memset(vis, 0, sizeof vis);

    int k = 0;

    for(int i = vs.size() - 1; i >= 0; i--)

        if(!vis[vs[i]]) rdfs(vs[i], k++);

    return k;

}

bool judge()

{

    int N = n;

    n = 2 * n;

    scc();

    for(int i = 0; i < 2 * N; i++)

        if(flag[i] == flag[i ^ 1]) return false;

    return true;

}

int main()

{

    while(~scanf("%d%d", &n, &m) && (n + m))

    {

        memset(G, 0, sizeof G);

        memset(rG, 0, sizeof rG);

        addedge(0, 1); // 新娘 -> 新郎

        for(int i = 0; i < m; i++)

        {

            int u, v;

            char c1, c2;

            scanf("%d%c%d%c", &u, &c1, &v, &c2);

            u *= 2; v *= 2;

            if(c1 == 'h') u ^= 1;

            if(c2 == 'h') v ^= 1;

            addedge(u, v ^ 1);

            addedge(v, u ^ 1);

        }

        if(!judge()) puts("bad luck");

        else

        {

            for(int i = 2; i < n; i += 2)

            {

                if(flag[i] > flag[i ^ 1])

                    printf("%dh", i / 2);

                else printf("%dw", i / 2);

                if(i >= n - 2) puts("");

                else printf(" ");

            }

        }

    }

    return 0;

}