hdu1816 Get Luffy Out * 题解


题意简述

有$2\cdot n$个钥匙,有$m$个门,每个门有两个钥匙孔只要一个打开这个门就被打开了,一把钥匙只能开一次,这$2\cdot n$个钥匙有$n$对,每对两把,一对钥匙只能用其中一个,这$m$个门必须按照给定顺序打开,问最多能开多少个门

题解

一个典型的2-sat模板,首先因为门必须按照顺序,所以可以直接二分前缀,对于二分得到的区间,我们勇2-sat建图,首先因为一组内只能用一把,那么对于一组$(a,b)$,可以连边$a\rightarrow ¬b$和$b\rightarrow ¬a$表示选了a就不能选b,选了b就不能选a
同理,对于门来说两个钥匙至少需要一个,那么连边$¬a\rightarrow b$和$¬b\rightarrow a$表示假如不选a一定要选b,假如选了b一定要选a
这样这道题就做完了,我用的拆点方法是把$¬a$拆成$a+2\cdot n$,建完图之后只需要判断2-sat是不是成立即可,代码是tarjan解法

AC代码

const int inf=0x3f3f3f3f;
const int maxn=10010;
PII t[maxn],a[maxn];
int n,m;
int head[maxn],num;
int dfn[maxn],low[maxn],tot;
int sta[maxn],insta[maxn],s,c,co[maxn];
struct node{
    int v,nex;
}e[maxn];
void add(int u,int v)
{
    e[++num].nex=head[u];
    e[num].v=v;
    head[u]=num;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++tot;
    sta[++s]=u;insta[u]=1;
    for(int i=head[u];i;i=e[i].nex)
    {
        int v=e[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(insta[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        int t=-1;c++;
        do
        {
            t=sta[s--];
            insta[t]=0;
            co[t]=c;
        }
        while(t!=u);
    }
}
bool calc(int mid)
{
    memset(head,0,sizeof(head));num=0;
    memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
    memset(co,0,sizeof(co));
    memset(insta,0,sizeof(insta));
    tot=s=c=0;
    for(int i=1;i<=n;i++)
    {
        add(t[i].first,t[i].second+2*n);
        add(t[i].second,t[i].first+2*n);
    }
    for(int i=1;i<=mid;i++)
    {
        add(a[i].first+2*n,a[i].second);
        add(a[i].second+2*n,a[i].first);
    }
    for(int i=0;i<4*n;i++) if(!dfn[i]) tarjan(i);
    int flag=1;
    for(int i=0;i<2*n;i++)
    {
        if(co[i]==co[i+2*n]) 
        {
            flag=0;
            break;
        }
    }
    if(flag) return true;
    return false;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) break;
        for(int i=1;i<=n;i++)
        {
            int x,y;read(x),read(y);
            t[i]=make_pair(x,y);
        }
        for(int i=1;i<=m;i++)
        {
            int x,y;read(x),read(y);
            a[i]=make_pair(x,y);
        }
        int l=0,r=m;
        while(l<r)
        {
            int mid=l+r>>1;
            if(calc(mid)) l=mid;
            else r=mid-1;
        }
        cout<<l<<endl;
    }
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
  目录