poj 2090 Two-Stacks Solitaire

这道题不是特别简单，我自己考虑了很久，未果。于是希望在网络上找到参考，但是网上参考不多

题意：给一个数列，两个栈，要求数列从后往前依次入栈，问能否使出栈序列是不减的。（双栈排序）

分析：利用二分图染色法。

首先观察那些牌绝对不能压入同一个栈，若两个不能入同一栈则连一条边，然后根据二分图染色，看是否能构成二分图。如果不能直接输出impossible

两张牌i,j不能入同一栈的充要条件是，i>j>k（i最先入栈） && a[k]<a[i]<a[j]

然后根据每个点所染的颜色决定把每个牌压入哪个栈。然后模拟即可。

原代码：

//用图论的思想来做题
//二分图着色

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

#define maxn 250

struct
{
    int v,next;
}edge[maxn*maxn];

int n;
int stock[maxn], f[maxn];
int head[maxn], ecount, color[maxn], q[maxn];
int out[maxn];
bool ok;
int stk1[maxn], stk2[maxn];
int top1, top2, step;

inline int min(int a,int b){ return a<b?a:b; }

void input()
{
    for (int i =0; i < n; i++)
    {
        scanf("%d", &stock[i]);
        out[i] = stock[i];
    }
}

void addedge(int&a, int&b)
{
    edge[ecount].next = head[a];
    edge[ecount].v = b;
    head[a] = ecount++;
}

void bfs(int&s)
{
    int front =0;
    int rear =1;
    q[0] = s;
    color[s] =1;
    while (front != rear)
    {
        int a = q[front++];
        for (int i = head[a]; i !=-1; i = edge[i].next)
        {
            int b = edge[i].v;
            if (!color[b])
            {
                q[rear++] = b;
                color[b] =3- color[a];
            }
            else if (color[a] == color[b])
            {
                ok =false;
                return;
            }
        }
    }
}

void make(int i)
{
    int a = stock[i];
    bool did =true;
    while (did)
    {
        did =false;
        if (top1 >0&& stk1[top1 -1] ==out[step])
        {
            top1--;
            printf("pop 1\n");
            step++;
            did =true;
        }
        if (top2 >0&& stk2[top2 -1] ==out[step])
        {
            top2--;
            printf("pop 2\n");
            step++;
            did =true;
        }
    }
    if (i <0)
        return;
    if (color[i] ==1)
    {
        stk1[top1++] = a;
        printf("push 1\n");
    }
    else
    {
        stk2[top2++] = a;
        printf("push 2\n");
    }
}

void print()
{
    top1 = top2 =0;
    step =0;
    for (int i = n -1; i >=0; i--)
        make(i);
    make(-1);
}

void work()
{
    memset(head, -1, sizeof(head));
    f[0] = stock[0];

	int i;
    for (i =1; i < n; i++)
        f[i] = min(f[i -1], stock[i]);

    ecount =0;
    for (i =1; i < n -1; i++)
    {
        for (int j = i +1; j < n; j++)
        {
            if (stock[j] >= stock[i])
                continue;
            if (stock[j] > f[i -1])
            {
                addedge(i, j);
                addedge(j, i);
            }
        }
    }
    ok =true;
    memset(color, 0, sizeof(color));
    for (i =0; i < n; i++)
    {
        if (!color[i])
            bfs(i);
        if (!ok)
        {
            printf("impossible\n");
            return;
        }
    }
    print();
}

int main()
{
    //freopen("t.txt", "r", stdin);
	int t =0;
    while (scanf("%d", &n), n)
    {
        t++;
        printf("#%d\n", t);
        input();
        sort(out, out+ n);
        work();
    }
    return 0;
}

不知道哪里出错的代码。。：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>

#define MAXN 250
using namespace std;

struct
{
    int v,next;
}edge[MAXN*MAXN];    //待连线的边

//输入的原数组是a[]，排序后数组是b[]
int a[MAXN],b[MAXN];
int N; // 1 <= N <= 208
int f[MAXN];	//存放前i个输入中的最小值，判断能不能在一个栈中使用
int head[MAXN], ecount, color[MAXN], q[MAXN];
bool ok;
int stk1[MAXN], stk2[MAXN];
int top1, top2, step;

inline int min(int a,int b){ return a<b?a:b; }

//addedge
void addedge(int&a, int&b)
{
	//其实用一个二维数组会更容易
    edge[ecount].next = head[a];
    edge[ecount].v = b;
    head[a] = ecount++;
}

//bfs
void bfs(int&s)
{
    int front =0;
    int rear =1;
    q[0] = s;
    color[s] =1;
    while (front != rear)
    {
        int d = q[front++];
        for (int i = head[d]; i !=-1; i = edge[i].next)
        {
            int c = edge[i].v;
            if (!color[c])
            {
                q[rear++] = c;
                color[c] =3- color[d];
            }
            else if (color[d] == color[c])
            {
                ok =false;
                return;
            }
        }
    }
}

//make
void make(int i)
{
    int temp = a[i];
    bool did =true;
    while (did)
    {
        did =false;
        if (top1 >0&& stk1[top1 -1] ==b[step])
        {
            top1--;
            printf("pop 1\n");
            step++;
            did =true;
        }
        if (top2 >0&& stk2[top2 -1] ==b[step])
        {
            top2--;
            printf("pop 2\n");
            step++;
            did =true;
        }
    }
    if (i <0)
        return;
    if (color[i] ==1)
    {
        stk1[top1++] = temp;
        printf("push 1\n");
    }
    else
    {
        stk2[top2++] = temp;
        printf("push 2\n");
    }
}

//print
void print()
{
    top1 = top2 =0;
    step =0;
    for (int i = N-1; i >=0; i--)
        make(i);
    make(-1);
}

//work
void work()
{
	memset(head, -1, sizeof(head));
	f[0]=a[0];

	int i;

	//f[i]中存的相当于是前i次中最小的数
    for (i =1; i < N; i++)
        f[i] = min(f[i -1], a[i]);

	//连边
	ecount =0;	//边数
    for (i =1; i < N -1; i++)
    {
        for (int j = i +1; j < N; j++)
        {
            if (a[j] >= a[i])
                continue;

			//如果上一个 if 中a[j]<a[i]，这里又大于前[i-1]个输入中的最小值
			//证明有[i-1]中的某个k，j>i>k时，有a[k]<a[j]<a[i]
			//入栈顺序是j,i,k
            if (a[j] > f[i -1])
            {
                addedge(i, j);
                addedge(j, i);
            }
        }
    }

	ok=true;
    memset(color, 0, sizeof(color));
    for (i =0; i < N; i++)
    {
        if (!color[i])
            bfs(i);
        if (!ok)
        {
            printf("impossible\n");
            return;
        }
    }
    print();
}

int main()
{
	int i;
	int t=0;
	while(~scanf("%d",&N) && N!=0)
	{
		for(i=0;i<N;i++)
		{
			scanf("%d",&a[i]);
			b[i]=a[i];
		}
		printf("#%d\n", ++t);

		//排序b[]
		sort(b,b+N);

		work();
	}

	return 0;
}