POJ 3648 Wedding（2−SATトポロジ順序付け出力のいずれかの解決策）

6355 ワード

テーマリンク:http://poj.org/problem?id=3648
Description
Up to thirty couples will ated a wedding feast、at which they will be seated on eigther side of a long table.The bride and groom sit at one end、opposite each other、and the briide wears s abooraboorate headdress thaat keeps hefrom seeeing people on the same side as her.It isconsideded bad luck ahsband and wifeseaated on the same sime side the the tablble.Additionalle e e thethethetherererepapapapapapapapapapapapapapapadededededededededededededededededededededededededededededederererererererererererererererererererererererererererererererererererererererererepossible)and it is bad luck for the bride to see both members of such a pair.Your job is to arrange people the table so as to avoid any bad luck.
Input
The input consists of a number of test cases、フォローアップby a line containing 0.Each test case gives n，the number of couples，followed by the number of adulterous pairs，followwed by the pairs，in the form“4 h 2 w”（husband from coup le 4，wife from coup 2），or「10 w 4 w」，or「3 h 1 berrow.」 n - 1 with the bride and groom being 0 w and 0 h.
Output
For each case，output a single line containing a list of the people that Shout be seated on the same side as the bride.If there are several solutions，any one will do.If there is solution，output a line containk.back。
Sample Input

10 6
3h 7h
5w 3w
7h 6w
8w 3w
7h 3w
2w 5h
0 0

Sample Output

1h 2h 3w 4h 5h 6h 7h 8h 9h

ソurce
Waterloo Local Contact，2007.9.29
件名:
新しいカップルが結婚して、招待されました。 n夫婦に結婚式に行きます。長いテーブルがあります。テーブルの両側にしか座ってはいけません。
以下の要求を満たす必要があります。
1.夫婦は同じ側に座ってはいけません。
2.n夫婦の中には姦通関係（男性、男女、女性を含む）があるかもしれません。姦通関係がある場合は、同時に花嫁の反対側に座ってはいけません。
可能なプログラムがあれば、花嫁と同じ側の人を出力します。
PS:
解を求める時は新郎と同じ側の人を選んで、出力する時は交換して新婦の同じ側の人です。iとjが奸情があるなら、iからj'まで、jからiまでの辺を加えて、新郎の辺に新婦を加えて、必ず新郎を選ぶと表しています。この問題は花嫁を直接選ぶのは間違いやすいです。花嫁にも浮気があるかもしれないので、排除が必要です。
コードは以下の通りです

/*
1.        (1h 2h     ，  1h->2w    2h->1w)
2.      
3.     (               ，  ；    )
4.    (    )
5.    
6.      (          ，    (   )  )
  ，           ，    ，       
*/
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
//2-SAT      
const int MAXN = 1010;
const int MAXM = 100010;
struct Edge
{
    int to;
    int next;
} edge[MAXM];
int head[MAXN],tot;
void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong    1~scc
int Index,top;
int scc;
bool Instack[MAXN];
int num[MAXN];
void Tarjan(int u)//tarjan        
{
    int v;
    Low[u] = DFN[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        v = edge[i].to;
        if( !DFN[v] )
        {
            Tarjan(v);
            if(Low[u] > Low[v])Low[u] = Low[v];
        }
        else if(Instack[v] && Low[u] > DFN[v])
            Low[u] = DFN[v];
    }
    if(Low[u] == DFN[u])
    {
        scc++;
        do
        {
            v = Stack[--top];
            Instack[v] = false;
            Belong[v] = scc;
            num[scc]++;
        }
        while(v != u);
    }
}

//      
bool solvable(int n)//n    ,      
{
    memset(DFN,0,sizeof(DFN));
    memset(Instack,false,sizeof(Instack));
    memset(num,0,sizeof(num));
    Index = scc = top = 0;
    for(int i = 0; i < n; i++)
        if(!DFN[i])
            Tarjan(i);
    for(int i = 0; i < n; i += 2)
    {
        if(Belong[i] == Belong[i^1])
            return false;
    }
    return true;
}

//            
queue<int>q1,q2;
vector<vector<int> > dag;//      DAG 
char color[MAXN];//  ， 'R'    
int indeg[MAXN];//  
int cf[MAXN];
void topsort(int n)
{
    dag.assign(scc+1,vector<int>());
    memset(indeg,0,sizeof(indeg));
    memset(color,0,sizeof(color));
    for(int u = 0; u < n; u++)//       
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].to;
            if(Belong[u] != Belong[v])
            {
                dag[Belong[v]].push_back(Belong[u]);
                indeg[Belong[u]]++;
            }
        }
    for(int i = 0; i < n; i += 2)
    {
        cf[Belong[i]] = Belong[i^1];
        cf[Belong[i^1]] = Belong[i];
    }
    while(!q1.empty())q1.pop();
    while(!q2.empty())q2.pop();
    for(int i = 1; i <= scc; i++)
        if(indeg[i] == 0)
            q1.push(i);
    while(!q1.empty())
    {
        int u = q1.front();
        q1.pop();
        if(color[u] == 0)
        {
            color[u] = 'R';
            color[cf[u]] = 'B';
        }
        int sz = dag[u].size();
        for(int i = 0; i < sz; i++)
        {
            indeg[dag[u][i]]--;
            if(indeg[dag[u][i]] == 0)
                q1.push(dag[u][i]);
        }
    }
}
int change(char s[])
{
    int ret = 0;
    int i = 0;
    while(s[i]>='0' && s[i]<='9')
    {
        ret *= 10;
        ret += s[i]-'0';
        i++;
    }
    if(s[i] == 'w') // 
        return 2*ret;
    else            // 
        return 2*ret+1;
}
int main()
{
    int n, m;
    char s1[17], s2[17];
    while(~scanf("%d%d",&n,&m))
    {
        if(n == 0 && m == 0)
            break;
        init();
        while(m--)
        {
            scanf("%s%s",s1,s2);
            int u = change(s1);
            int v = change(s2);
            addedge(u^1,v);//    ,    
            addedge(v^1,u);
        }
        addedge(1,0);
        if(solvable(2*n))//      
        {
            topsort(2*n);
            for(int i = 1; i < n; i++)
            {
                //        color[Belong[
                if(color[Belong[2*i]] == 'R')
                    printf("%dw",i);
                else
                    printf("%dh",i);
                if(i < n-1)
                    printf(" ");
                else
                    printf("
");
            }
        }
        else
            printf("bad luck
");
    }
    return 0;
}

Javaの単一の例のモードの実現方式とその長所と短所――単一の例のモードはまたこのように実現することができる。

アセンブリ言語はどんなプログラム設計言語ですか？