BZOJ 1854 [SCOI2010]游戏

题目大意

你有一堆东西，每个东西有两个属性，你只能在这两个属性中选择一个，求生成的最长连续上升序列长度。

这道题我自己想到了可以用2-SAT二分图最大匹配来解决，但是最开始的时候却想要去把每一个物品的两个属性拆成两个对立点来解决。这样虽然有效的解决了“不能一种物品的两种属性都选中”的这一要求，但是有出现了一个“属性相差1的物品的属性选择不能是同一选择”的蛇皮条件。

**二分图最大匹配的两侧不是同种元素。**所以自然的想到要用另外的方法：直接把连续的目标属性放在一边，把东西放在另一边，之后跑一次匈牙利就可以了。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,a[1000010],b[1000010],pr[1000010],ans,use[1000010];
bool xyl(int pos)
{
    for(int i=1;i<=n;++i)
        if((a[i]==pos-n||b[i]==pos-n)&&use[i]!=ans)
        {
            use[i]=ans;
            if(!pr[i]||xyl(pr[i]))
            {
                pr[i]=pos;
                return true;
            }
        }
    return false;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",a+i,b+i);
    while(++ans)
        if(!xyl(ans+n))
        {
            printf("%d\n",ans-1);
            return 0;
        }
}