P1155 双栈排序（二分图的染色判断+链式前向星）

P1155 双栈排序

让字典序最小，当然尽量进S1
那什么时候必须进S2呢？
a[i]和a[j] 不能压入同一个栈⇔存在一个k,使得i<j<k且a[k]<a[i]<a[j]
因为一个数只能进出一次，k要排在前面所以弹出k时i和j都在栈里，如果两者在同一个栈弹出后顺序就错误了
对于任意两个数t[i]和t[j],它们不能压入同一个栈中的充要条件: 存在一个k,使得i<j<k且t[k]<t[i]<t[j]。
证明 ：利用反证法，假设当这t[i]，t[j]压入了同一个栈，那么压入t[k]，因为t[k]<t[i]<t[j]，显然，当t[k]没有被弹出的时候，另两个数也都不能被弹出，否则不符题意。而又因t[j]总是会在t[i]之前弹出，但t[j]>t[i]，矛盾，所以假设不成立。
由此，我们便可根据这些来解决此题了。
这样i和j连一条边然后二分图染色再用栈模拟就行了，因为数据是1…n维护cur表示当前该弹出哪个数字
PS：1.建图时先DP用f[i]表示i…n中最小元素
　　2.二分图染色可以解决一些有关系，分成两类的问题　
题解参考
本题中使用链式前向星存二分图
链式前向星

#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout<<"#  "<<x<<" "<<endl;
typedef long long ll;
const ll mod=2147483647;
const ll N=1e4+7;
ll n,a[N],h[N],cnt,f[N];
struct edge
{
    ll v,ne;
}G[N*N];//邻接表创建二分图
//把u和v连在一起二分图里一条边连起来的两个端点是分别在两个集合中的
inline void init(ll u,ll v)
{
    cnt++;
    G[cnt].v=v;G[cnt].ne=h[u];h[u]=cnt;
    cnt++;
    G[cnt].v=u;G[cnt].ne=h[v];h[v]=cnt;
}
inline void dp()
{
    //f[i]表示i..n中最小元素
    f[n]=a[n];
    for(int i=n-1;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)
            //如果存在k,满足i<j<k&&a[k]<a[i]<a[j],那么i和j是不能存在一边的集合中的
            if(a[i]<a[j]&&f[j]<a[i])
                init(i,j);
}
ll col[N];
bool color(ll u,ll c)
{
    col[u]=c;
    for(int i=h[u];i;i=G[i].ne)
    {
        ll v=G[i].v;
        if(col[v]==col[u])return false;
        if(!col[v]&&!color(v,3-c))return false;
    }
    return true;
}
ll s1[N],s2[N],t1,t2;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
    dp();
    for(int i=1;i<=n;++i)
        if(!col[i]&&!color(i,1))
        {
            puts("0");
            return 0;
        }
    ll cur=1;
    for(int i=1;i<=n;++i)
    {
        if(col[i]==1)
            s1[++t1]=a[i],cout<<"a ";
        else s2[++t2]=a[i],cout<<"c ";
        //输入的数是1~n 的
        while(s1[t1]==cur||s2[t2]==cur)//边入边出
        {
            if(s1[t1]==cur)cout<<"b ",t1--;
            else cout<<"d ",t2--;
            cur++;
        }
    }
    cout<<endl;
    return 0;
}