首页 > ACM题库 > HDU-杭电 > hdu 2063 过山车-二分图-[解题报告]C++
2013
12-29

hdu 2063 过山车-二分图-[解题报告]C++

过山车

问题描述 :

RPG girls今天和大家一起去游乐场玩,终于可以坐上梦寐以求的过山车了。可是,过山车的每一排只有两个座位,而且还有条不成文的规矩,就是每个女生必须找个个男生做partner和她同坐。但是,每个女孩都有各自的想法,举个例子把,Rabbit只愿意和XHD或PQK做partner,Grass只愿意和linle或LL做partner,PrincessSnow愿意和水域浪子或伪酷儿做partner。考虑到经费问题,boss刘决定只让找到partner的人去坐过山车,其他的人,嘿嘿,就站在下面看着吧。聪明的Acmer,你可以帮忙算算最多有多少对组合可以坐上过山车吗?

输入:

输入数据的第一行是三个整数K , M , N,分别表示可能的组合数目,女生的人数,男生的人数。0<K<=1000
1<=N 和M<=500.接下来的K行,每行有两个数,分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。

输出:

输入数据的第一行是三个整数K , M , N,分别表示可能的组合数目,女生的人数,男生的人数。0<K<=1000
1<=N 和M<=500.接下来的K行,每行有两个数,分别表示女生Ai愿意和男生Bj做partner。最后一个0结束输入。

样例输入:

6 3 3
1 1
1 2
1 3
2 1
2 3
3 1
0

样例输出:

3

二分图的基本概念 一个无向图G=<V, E>,如果存在两个集合X、Y,使得X∪Y=V, X∩Y=Φ,并且每一条边e={x,y}有x∈X,y∈Y,则称G为一个二分图(bipartite graph)。常用<X, E, Y>来表示一个二分图。若对X中任一x及Y中任一y恰有一边e∈E,使e = {x, y}, 则称G为完全二分图(complete bipartite graph)。当|X| = m,|Y| = n时,完全二分图G记为Km,n

二分图的性质: 定理:无向图G为二分图的充分必要条件是,G至少有两个顶点,且其所有回路的长度均为偶数。 匹配:设G=<V, E>为二分图,如果M⊆E,并且M中没有任何两边有公共端点。M=Φ时称M为空匹配。 最大匹配:G的所有匹配中边数最多的匹配称为最大匹配。 完全匹配:若X(Y)中所有的顶点都是匹配M中的端点。则成M为完全匹配。若M既是X-完全匹配又是Y-完全匹配,则称M为G的完全匹配。 注意:最大匹配总是存在但未必唯一;X(Y)-完全匹配及G的完全匹配必定是最大的,但反之则不然;X(Y)-完全匹配未必存在。

下面引入几个术语: 设G=<V, E>为二分图,M为G的一个匹配。

  1. M中边的端点称为M-顶点,其它顶点称为非M-顶点
  2. 增广路径:除了起点和终点两个顶点为非M-顶点,其他路径上所有的点都是M=顶点。而且它的边为匹配边、非匹配边交替出现。

hdu 2063 过山车  简单的二分图最大匹配

   题目连接:  http://acm.hdu.edu.cn/showproblem.php?pid=2063

                   http://poj.org/problem?id=2226

代码如下:

#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define MAX 510
bool flag[MAX];
int map[MAX][MAX],mark[MAX];
int k,b,g;
bool dfs(int x)
{

    for(int i=1;i<=b;i++)
    {
        if(!map[x][i]||flag[i])//如果这两点没边 或有边但被标记过了就继续循环
            continue;
        flag[i]=1;   
        if(!mark[i]||dfs(mark[i])) //如果该点是孤立点或者不是孤立点时就搜索该点对应女生的增广路
        {
            mark[i]=x;
            return 1;
        }
    }
    return 0;
}
int find()
{
    int i,sum=0;
    memset(mark,0,sizeof(mark));
    for(i=1;i<=g;i++)
    {
        memset(flag,0,sizeof(flag));
        if(dfs(i))
            sum++;
    }
    return sum;
}
int main()
{
    int x,y;
    while(scanf("%d",&k)!=EOF)
    {
        if(k==0) break;
        scanf("%d%d",&g,&b);
        memset(map,0,sizeof(map));
        for(int i=1;i<=k;i++)
            {
                scanf("%d%d",&x,&y);
                map[x][y]=1;
            }
        printf("%d\n",find());
    }
    return 0;
}

 

//poj 2226
#include <iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define MAX 900
bool flag[MAX];
int map[MAX][MAX],mark[MAX],cx[MAX][MAX],cy[MAX][MAX];
char a[MAX][MAX];
int n,m,nx,ny;
bool dfs(int x)
{
    for(int i=1;i<=ny;i++)
    {
        if(!map[x][i]||flag[i])//如果这两点没边 或有边但被标记过了就继续循环
            continue;
        flag[i]=1;
        if(!mark[i]||dfs(mark[i])) //如果该点是孤立点或者不是孤立点时就搜索该点对应女生的增广路
        {
            mark[i]=x;//标记该点连接的边
            return 1;
        }
    }
    return 0;
}
int find()
{
    int i,sum=0;
    memset(mark,0,sizeof(mark));
    for(i=1;i<=nx;i++)
    {
        memset(flag,0,sizeof(flag));
        if(dfs(i))
            sum++;
    }
    return sum;
}
int main()
{
    int i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        getchar();
        for(i=1;i<=n;i++)
        {

            for(j=1;j<=m;j++)
                a[i][j]=getchar();
            getchar();
        }
        nx=ny=0;
        for(i=1;i<=n;i++)
        {
            j=1;
            while(j<=m)
            {
            if(a[i][j]=='*')
            {
                nx++;
                while(a[i][j]=='*')
                    cx[i][j++]=nx;
            }
            else j++;
            }
        }
        for(j=1;j<=m;j++)
        {
            i=1;
            while(i<=n)
            {
            if(a[i][j]=='*')
            {
                ny++;
                while(a[i][j]=='*')
                    cy[i++][j]=ny;
            }
            else i++;
            }
        }
        memset(map,0,sizeof(map));
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            if(a[i][j]=='*') map[cx[i][j]][cy[i][j]]=1;
        printf("%d\n",find());
    }
    return 0;
}

 

解题转自:http://www.cnblogs.com/yly921712230/p/3227418.html


  1. “可以发现,树将是满二叉树,”这句话不对吧,构造的树应该是“完全二叉树”,而非“满二叉树”。

  2. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。