题意

一个皇帝有数个儿子(约2000个吧...)每个儿子喜欢数个女孩(约100)个吧。女孩数量和儿子数量相同。现在题目输入已经给出一种方案,使得每个儿子可以匹配到一个他喜欢的女孩,女孩不相互重复(即一个合法的完备匹配)。求所有完备匹配中每个儿子分别可以选择哪写女孩(即某个儿子选择了某个喜欢的女孩后仍然存在完备匹配)。

分析

虽然匈牙利算法可以求出完备匹配,但是对于所有完备匹配的特性无能为力。于是我们从题目给出的完备匹配出发,寻找突破口。
这个里面的话,只要看一眼题解,大家差不多就都懂了。
我们将将每个儿子向它喜欢的每个女孩连单向边,每个女孩向当前匹配的儿子连单向边。
考察匈牙利算法求解增广路的方式。如果我们从一个点出发,来回遍历对偶图,直到回到原点,获得一个新的增广路,这就成为了匹配的一部分。而对于一个完备匹配,如果我们从一个点出发,来回遍历对偶图,直到回到原点,获得一个新的增广路,并按增广路来更新匹配,我们就可以获得一个新的完备匹配。
因此我们可以证明:
    1.一个完备匹配通过一条增广路获得一个新的完备匹配
    2.每一个完备匹配都可以通过其他完备匹配增广得到
    3.由一个完备匹配可以增广得到所有完备匹配。
于是,我们需要寻找增广路有关的特性。
大多数题解中都提到了这样一个词(哈哈这篇也是):强联通分量。一个点若需要增广并回到原点,增广路经过的点一定是在一个强联通分量里的。
因此我们可以证明:
    1.从一个儿子出发回到这个儿子的增广路只经过这个儿子所在的强联通分量
    2.从一个儿子出发,先到任意一个女孩都可以回到这个儿子(根据强联通的特性)。
这样,我们就证明了一个儿子如果选择了某个和他在同一个强联通分量里的女孩,都使全局存在一个合法的完备匹配。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define ME 202004
#define MN 4002

using namespace std;

int fst[MN],nxt[ME],v[ME],lnum;
int ans[MN];
int n;

inline void addeg(int nu,int nv)
{
    nxt[++lnum]=fst[nu];
    fst[nu]=lnum;
    v[lnum]=nv;
}

inline void input()
{
    int a,b;
    for(register int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        for(register int j=1;j<=a;j++)
        {
            scanf("%d",&b);
            addeg(i,b+n);
        }
    }
    for(register int i=1;i<=n;i++)
    {
        scanf("%d",&b);
        addeg(b+n,i);
    }
}

int dfn[MN],low[MN];
int stk[MN],top,vnum,cnum;
int color[MN];

void tarjan(int x)
{
    dfn[x]=low[x]=++vnum;
    stk[++top]=x;
    for(register int i=fst[x];i!=-1;i=nxt[i])
    {
        if(!dfn[v[i]])
        {
            tarjan(v[i]);
            low[x]=min(low[x],low[v[i]]);
        }
        else if(!color[v[i]])low[x]=min(low[x],dfn[v[i]]);
    }
    if(low[x]==dfn[x])
    {
        cnum++;
        for(;;)
        {
            int a=stk[top--];
            color[a]=cnum;
            if(a==x)break;
        }
    }
}

inline void work()
{
    for(register int i=1;i<=n*2;i++)if(!dfn[i])tarjan(i);
    for(register int i=1;i<=n;i++)
    {
        register int anum=0;
        for(register int j=fst[i];j!=-1;j=nxt[j])
            if(color[i]==color[v[j]])
                ans[++anum]=v[j]-n;
        sort(ans+1,ans+anum+1);
        printf("%d ",anum);
        for(register int j=1;j<=anum;j++)printf("%d ",ans[j]);
        printf("\n");
    }
}

inline void init()
{
    memset(fst,0xff,sizeof(fst));
    memset(dfn,0,sizeof(dfn));
    top=vnum=cnum=0;
    lnum=-1;
}

int main()
{
    while(~scanf("%d",&n))
    {
        init();
        input();
        work();
    }
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *