P1155 双栈排序 二分图染色问题
查看原帖
P1155 双栈排序 二分图染色问题
372454
AsadChen楼主2022/8/6 12:11

我甚至照不出来错在哪里

#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 1010;

int n, k, tot, sum = 1, p1 = N, p2 = N;
int a[N], f[N], color[N], t[N];
//a存储排列,f用于存储某个元素后的最小值,c存颜色,t存操作
char s[5] = {'0', 'a', 'b', 'c', 'd'}; //各种输出
int e[N], h[N], ne[N], idx;

vector<int> p[N]; //记录某一个点的边
queue<int> q; //二分图染色法用

stack <int> s1, s2; //双栈

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int main()
{
    scanf("%d", &n);

    f[n + 1] = n + 1; //初始化
    memset(h, -1, sizeof h);

    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for (int i = n; i >= 1 ; i--) f[i] = min(f[i + 1], a[i]);
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (a[i] < a[j] && a[i] > f[j + 1])
            {
                //建立二分图
                add(i, j);
                add(j, 1);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!color[i])
        {
            //没有染色
            q.push(i);
            color[i] = 1; //该点进入s1
            while (!q.empty())
            {
                int now = q.front();
                q.pop();
                for (int j = h[now]; j != -1; j = ne[j])
                {
                    int y = e[i];
                    if (color[y])
                    {
                        if (color[y] ^ color[now]) continue; //染色了而且不渣
                        printf("0");
                        return 0;
                    }
                    color[y] = color[now] * (-1);
                    q.push(y);
                }
            }
        }
    }

    int i = 1;
    while (k < 2 * n)
    {
        if (!s1.empty()) p1 = s1.top();
        if (!s2.empty()) p2 = s2.top();

        if (color[i] == 1 && (a[i] < p1 || s2.empty()))
        {
            s1.push(a[i]);
            t[++k] = 1;
            i++;
        }
        else if (p1 == sum)
        {
            sum++;
            t[++k] = 2;
            s1.pop();
        }
        else if (color[i] == -1 && (a[i] < p2 || s2.empty()))
        {
            s2.push(a[i]);
            t[++k] = 3;
            i++;
        }
        else if (p2 == sum)
        {
            sum++;
            t[++k] = 4;
            s2.pop();
        }
    }

    for (int i = 1; i < 2 * n; i++)
    {
        printf("%c", s[t[i]]);
    }

    return 0;
}

2022/8/6 12:11
加载中...