题解 P2055 【[ZJOI2009]假期的宿舍】

· · 题解

【题目描述】

学校放假了......有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如A和B都是学校的学生，A要回家，而C来看B，C与A不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是B睡A的床而C睡B的床。而实际情况可能非常复杂，有的人可能认识好多在校学生，在校学生之间也不一定都互相认识。我们已知一共有n个人，并且知道其中每个人是不是本校学生，也知道每个本校学生是否回家。问是否存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。

【输入输出格式】

第一行一个数T表示数据组数。接下来T组数据，每组数据第一行一个数n表示涉及到的总人数。接下来一行n个数，第i个数表示第i个人是否是在校学生(0表示不是，1表示是)。再接下来一行n个数，第i个数表示第i个人是否回家(0表示不回家，1表示回家，注意如果第i个人不是在校学生，那么这个位置上的数是一个随机的数，你应该在读入以后忽略它)。接下来n行每行n个数，第i行第j个数表示i和j是否认识(1表示认识，0表示不认识，第i行i个的值为0，但是显然自己还是可以睡自己的床)，认识的关系是相互的。

对于每组数据，如果存在一个方案则输出“^_^”(不含引号)否则输出“T_T”(不含引号)。(注意输出的都是半角字符，即三个符号的 ASCII 码分别为94,84,95)。

【输入输出样例】

1
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0

^_^

【数据范围】

对于30%的数据满足1 \leq n \leq 12。

对于100%的数据满足1 \leq n \leq 50，1 \leq T \leq 20。

思路：

这道题很明显就是一道二分图的最大匹配问题，当然这道题也可以用网络流来做，在讲完二分图匹配的思路后就会讲解最大流的思路了。你可以在这里检测你码的二分图最大匹配的模板的正确性。下面将详细地讲解二分图最大匹配这一算法。这里提出的二分图最大匹配问题与洛谷上的模板略有不同。如果你还没有理解什么是二分图匹配的话，那么就去学习下面的教程吧（教程转自《啊哈！算法》，放入题解时有删改）。

小哼今天和小伙伴们一起去游乐场玩，终于可以坐上梦寐以求的过山车了。过山车的每一排只有两个座位，为了安全起见，每个女生必须与一个男生坐一排。但是，每个人都希望与自己认识的人坐在一起。举个例子吧，1好女生与1号男生互相认识，因此1号女生可以和1好男生坐在一起。另外1号女生与2号男生互相认识，因此他们也可以坐在一起。像这样的关系的还有2号女生和2号男生、2号女生和3号男生、3号女生和1号男生。请问如何安排座位才能让更多的人满意呢？这仅仅是个例子。实际情况要复杂得多，因为小哼的小伙伴们实在是太多了。

首先我们先将这个问题模型化，如上图，左边的顶点是女生，右边的顶点是男生。如果顶点之间右边，就表示他们可以坐在一起，像这样特殊的图叫做二分图（注意二分图是无向图哦）。对于上面的例子，我们很容易找出两种分配方案，如下。

  1. 如果一个图的所有的顶点都可以被分成x和y两个集合，并且所有边的两个顶点恰好属于一个集合x，另一个属于集合y，即每个集合内的顶点没有边相连，那么这张图就是二分图。

  2. 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i ∈ A,j ∈ B)，则称图G为一个二分图。

很显然，右边的分配方案更好。我们把一种分配方案叫做一种匹配。那么现在的问题就演变成了求二分图的最大匹配（匹配对数多）。求最大匹配容易想到的办法是：找出全部匹配，然后输出配对数最多的。这种方法的时间复杂度是非常之高的，那还有没有更好的办法呢？ 我们可以这么想，首先先从左边的1号女生开始考虑。先让她与1号男生配对，配对成功后就考虑2号女生与2号男生配对，接下来考虑3号女生。此时我们发现3号女生只能够跟1号男生配对，可是1号男生已经配对给了1号女生了，怎么办？其实我们可以让3号女生跟1号男生谈。让与1号男生相配对的1号女生一起谈，看看一号女生能不能够找到其他的同伴。如果能够找到，就让3号女生与1号男生坐在一起，让1号女生与1号女生相配对的那个人坐在一起，若1号女生找到的其他的可以与1号女生配对的人已经有同伴的话就让他的同伴去找，看看其他人能否作为她的同伴，然后以此类推。若第i名男生找到了同伴，就将答案加1。刚才的匹配过程就叫做增广路，不难发现，只要找到了一条增广路答案就会加1，最后只需要输出答案即可。 下面给出两组数据用于检测您的程序的正确性（注：1到3号是男生，4到6号是女生）：

6 5
1 4
1 5
2 5
2 6
3 4

3
6 4
1 4
2 5
2 6
3 4

3

下面就是二分图最大匹配的模板：

#include <cstdio>
int book[10001];
int match[10001];
bool e[101][101];
int ans=0,n=0,m=0;
bool dfs(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(book[i]==0 && e[u][i]==true)
        {
            book[i]=1;
            if(match[i]==0 || dfs(match[i])==true)
            {
                match[u]=i;
                match[i]=u;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x=0,y=0;
        scanf("%d %d",&x,&y);
        e[x][y]=true;
        e[y][x]=true;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            book[j]=0;
        }
        if(dfs(i)==true)
        {
            ans++;
        }
    }
    printf("%d",ans);
    return 0;
}

那么既然二分图最大匹配的思路讲完了，我们就要开始尝试去用二分图最大匹配来解决这道题目了。我们可以把人分给床。下面是几种情况：

  1. 如果他在学校住并且是本校学生，那么就让他睡回自己的床。

  2. 如果他在不在学校住或者他不回家，且他找不到自己的床。那么就返回false，false表示不存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住，否则当返回true时就表示存在一个方案使得所有不回家的本校学生和来看他们的其他人都有地方住。

  3. 如果他可以和这张床配对（即他认识这张床的主人），如果现在还没有人和这张床配对的话就直接让他和这张床配对，否则就看看现在与这张床配对的人可不可以找到另一张床可以和他配对，如果可以就让那个原本和那张床配对的人去和他找到的另一张可以与他配对的床相配对。再让这张现在没有配对的人与一开始提到的那个人相配对。

下面是一些注意事项：

  1. 是人认识床的主人，所以才能够睡在这张床上。所以连的是单向边，不是双向边。

  2. 要初始化，因为有多组数据。

讲完了二分图匹配的思路，下面就讲一讲网络流的思路吧，如下。你可以在这里检验你的网络流模板的正确性。下面将详细地讲解网络流这一算法。

对于下图，我们很容易就能够看出来这是一张单向图。

现在，我们给这几条边标上流量（也可以说是边权或者是最大流量）。注意，现在要标上流量的是边而不是点。什么是流量？我们不妨把从x点到y点的最大流量当做从x点到y点可以流过去的最大的水的重量，求从起始点处打开水龙头，让水通过这些“水管”（即边）流到到结束点处。现在我们的问题是，有n个点m条边，求源点到汇点的最大流量是多少。源点即起点，汇点即终点。在这里，我们的源点是1，汇点是点2。

下面我们给这些点标层，如下。

你会发现那些没有被标到层的都是无法到达的。于是我们便可以用广搜来判断能否到达汇点，若能够到达就计算有多少的流量能够流到汇点即可，当然，前提是还有水可以流过去。但是我们要注意一点：流过去的水如果留不到汇点还会流回来，因此我们对每一条单向边建一条流量为0的反向边即可，当有水流回来的时候加上反向边的流量即可。还有一点要注意的是，因为我们流水过去到汇点的次数可能会有多次，所以我们要加一个循环来完成网络流的整个过程。

下面上网络流的模板，你可以根据网络流的模板来进行进一步的学习，同时也感谢@liusu201601的建议。

#include <cstdio>
#include <cstring>
#include <cstdlib>
struct nodea{ int x,y,d,g,f; } e[2000002];
struct nodeb{ int first,h; } r[1000001];
int q[1000001],len=0,m=0,n=0,st=0,ed=0;
int min(int x,int y)
{
    return x<y?x:y;
}
void ins(int x,int y,int d)
{
    len++;

    e[len].x=x;
    e[len].y=y;
    e[len].d=d;
    e[len].g=r[x].first;
    r[x].first=len;

    len++;

    e[len].x=y;
    e[len].y=x;
    e[len].d=0;
    e[len].g=r[y].first;
    r[y].first=len;

    e[len].f=len-1;
    e[len-1].f=len;
}
bool bfs()
{
    int tou=1,wei=2;
    for(int i=1;i<=n;i++)
    {
        r[i].h=0;
    }
    r[st].h=1;

    memset(q,0,sizeof(q));
    q[1]=st;

    while(tou!=wei)
    {
        int x=q[tou];
        for(int i=r[x].first;i>0;i=e[i].g)
        {
            int y=e[i].y;
            if(e[i].d>0 && r[y].h==0)
            {
                r[y].h=r[x].h+1;
                q[wei]=y;
                wei++;
            }
        }
        tou++;
    }
    if(r[ed].h>0)
    {
        return true;
    }
    return false;
}
int dfs(int x,int f)
{
    if(x==ed)
    {
        return f;
    }
    int tt=0;
    for(int i=r[x].first;i>0;i=e[i].g)
    {
        int y=e[i].y;
        if(r[x].h+1==r[y].h && tt<=f && e[i].d>0)
        {
            int my=dfs(y,min(e[i].d,f-tt));
            tt+=my;
            e[i].d-=my;
            e[e[i].f].d+=my;
        }
    }
    if(tt==0)
    {
        r[x].h=0;
    }
    return tt;
}
int main()
{
    scanf("%d %d %d %d",&n,&m,&st,&ed);
    for(int i=1;i<=m;i++)
    {
        int x=0,y=0,d=0;
        scanf("%d %d %d",&x,&y,&d);
        ins(x,y,d);
    }
    int ans=0;
    while(bfs()==true)
    {
        ans+=dfs(st,2099999999);
    }
    printf("%d",ans);
    return 0;
}

那么，对于网络流，该如何建图呢？

  1. 将人与源点连线，并将床与汇点连线。在这里，我用i来表示第i个人，用i+n来表示第i张床。

  2. 若一个人有床（即这个人是在下学生）就将这张床与汇点连线。若一个人需要床（即是本校学生的好朋友或是本校学生在这里住），就将其与源点相连线。若i认识j，那么i就可以睡j的床，那么就将i和j的床相连线，即将i和j+n相连线。

  3. 因为有多组数据，要注意将数组都初始化。一开始我就因为有两个数组忘了初始化造成了死循环，但是将这几组数据拆开后又是对的，这可能就是你的初始化没有初始化好了。一开始我就是因为没有初始化错了好几次，后来才通过的。

下面上100分代码~

二分图匹配：

#include <cstdio>
#include <cstring>
int book[10001];
int match[10001];
int e[101][101];
int rn[10001],ho[10001];
int ans=0,n=0;
bool dfs(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(book[i]==0 && rn[i]==1 && e[u][i]==1)
        {
            book[i]=1;
            if(match[i]==0 || dfs(match[i])==true)
            {
                match[i]=u;
                return true;
            }
        }
    }
    return false;
}
bool work()
{
    for(int i=1;i<=n;i++)
    {
        memset(book,0,sizeof(book));
        if((rn[i]==0 || ho[i]==0) && (dfs(i)==false))
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int t=0;
    scanf("%d",&t);
    while(t--)
    {
        ans=0;
        memset(book,0,sizeof(book));
        memset(match,0,sizeof(match));
        memset(rn,0,sizeof(rn));
        memset(ho,0,sizeof(ho));
        memset(e,0,sizeof(e));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&rn[i]);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&ho[i]);
            if(rn[i]==0)
            {
                ho[i]=1;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&e[i][j]);
            }
            if(rn[i]==1)
            {
                e[i][i]=1;
            }
        }
        if(work()==true)
        {
            printf("^_^\n");
        }
        else
        {
            printf("T_T\n");
        }
    }
    return 0;
}

网络流：

#include <cstdio>
#include <cstring>
#include <cstdlib>
struct nodea{ int x,y,d,g,f; } e[1000001];
struct nodeb{ int first,h; } r[1000001];
int inf=999999999,st=1001,ed=1002,n=0;
int q[1000001],len=0;
int min(int x,int y)
{
    return x<y?x:y;
}
void ins(int x,int y,int d)
{
    len++;

    e[len].x=x;
    e[len].y=y;
    e[len].d=d;
    e[len].g=r[x].first;
    r[x].first=len;

    len++;

    e[len].x=y;
    e[len].y=x;
    e[len].d=0;
    e[len].g=r[y].first;
    r[y].first=len;

    e[len].f=len-1;
    e[len-1].f=len;
}
bool bfs()
{
    int tou=1,wei=2;
    for(int i=1;i<=2000;i++)
    {
        r[i].h=0;
    }
    r[st].h=1;
    r[ed].h=0;

    q[1]=st;

    while(tou<wei)
    {
        int x=q[tou];
        for(int i=r[x].first;i>0;i=e[i].g)
        {
            int y=e[i].y;
            if(e[i].d>0 && r[y].h==0)
            {
                r[y].h=r[x].h+1;
                q[wei]=y;
                wei++;
            }
        }
        tou++;
    }
    if(r[ed].h>0)
    {
        return true;
    }
    return false;
}
int dfs(int x,int f)
{
    if(x==ed)
    {
        return f;
    }
    int tt=0;
    for(int i=r[x].first;i>0;i=e[i].g)
    {
        int y=e[i].y;
        if(r[x].h+1==r[y].h && tt<=f && e[i].d>0)
        {
            int my=dfs(y,min(e[i].d,f-tt));
            tt+=my;
            e[i].d-=my;
            e[e[i].f].d+=my;
        }
    }
    if(tt==0)
    {
        r[x].h=0;
    }
    return tt;
}
int dinic()
{
    int ans=0;
    while(bfs()==true)
    {
        ans+=dfs(st,inf);
    }
    return ans;
}
int main()
{
    int t=0;
    scanf("%d",&t);
    while(t--)
    {
        int tot=0;
        scanf("%d",&n);
        memset(q,0,sizeof(q));
        memset(e,0,sizeof(e));
        memset(r,0,sizeof(r));
        len=0;
        int rn[101],ho[101];
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&rn[i]);
            if(rn[i]==1)
            {
                ins(i+n,ed,1);
            }
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&ho[i]);
            if((rn[i]==1 && ho[i]==0) || (rn[i]==0))
            {
                ins(st,i,1);
                tot++;
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                int dx=0;
                scanf("%d",&dx);
                if(dx==1 || i==j)
                {
                    ins(i,j+n,1);
                }
            }
        }
        if(dinic()>=tot)
        {
            printf("^_^\n");
        }
        else
        {
            printf("T_T\n");
        }
    }
    return 0;
}