首页 > ACM题库 > HDU-杭电 > hdu 2458 Kindergarten-动态规划-[解题报告]C++
2014
01-26

hdu 2458 Kindergarten-动态规划-[解题报告]C++

Kindergarten

问题描述 :

In a kindergarten, there are a lot of kids. All girls of the kids know each other and all boys also know each other. In addition to that, some girls and boys know each other. Now the teachers want to pick some kids to play a game, which need that all players know each other. You are to help to find maximum number of kids the teacher can pick.

输入:

The input consists of multiple test cases. Each test case starts with a line containing three integers
G, B (1 ≤ G, B ≤ 200) and M (0 ≤ M ≤ G × B), which is the number of girls, the number of boys and
the number of pairs of girl and boy who know each other, respectively.
Each of the following M lines contains two integers X and Y (1 ≤ X≤ G,1 ≤ Y ≤ B), which indicates that girl X and boy Y know each other.
The girls are numbered from 1 to G and the boys are numbered from 1 to B.

The last test case is followed by a line containing three zeros.

输出:

The input consists of multiple test cases. Each test case starts with a line containing three integers
G, B (1 ≤ G, B ≤ 200) and M (0 ≤ M ≤ G × B), which is the number of girls, the number of boys and
the number of pairs of girl and boy who know each other, respectively.
Each of the following M lines contains two integers X and Y (1 ≤ X≤ G,1 ≤ Y ≤ B), which indicates that girl X and boy Y know each other.
The girls are numbered from 1 to G and the boys are numbered from 1 to B.

The last test case is followed by a line containing three zeros.

样例输入:

2 3 3
1 1
1 2
2 3
2 3 5
1 1
1 2
2 1
2 2
2 3
0 0 0

样例输出:

Case 1: 3
Case 2: 4


最小点覆盖==最大匹配

#include <queue>
#include <cstdio>
#include <cstdlib>
#include <iostream>

using namespace std;

const int maxn=210;
const int INF=0x7fffffff;

int n,m,dis;
int cx[maxn];
int cy[maxn];
int dx[maxn];
int dy[maxn];
bool vis[maxn];
bool map[maxn][maxn];

bool searchpath()
{
    queue<int> Q;
    for(int i=1;i<=m;i++)
        dy[i]=-1;
    for(int i=1;i<=n;i++)
    {
        dx[i]=-1;
        if(cx[i]==-1)
        {
            Q.push(i);
            dx[i]=0;
        }
    }
    dis=INF;
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        if(dx[u]>dis)
            break;
        for(int i=1;i<=m;i++)
        {
            if(dy[i]==-1&&map[u][i])
            {
                dy[i]=dx[u]+1;
                if(cy[i]==-1)
                    dis=cy[i];
                else
                {
                    dx[cy[i]]=dy[i]+1;
                    Q.push(cy[i]);
                }
            }
        }
    }
    return dis!=INF;
}

int findpath(int u)
{
    for(int i=1;i<=m;i++)
    {
        if(!vis[i]&&map[u][i]&&dy[i]==dx[u]+1)
        {
            vis[i]=true;
            if(dy[i]==dis&&cy[i]!=-1)
                continue;
            if(cy[i]==-1||findpath(cy[i]))
            {
                cx[u]=i;
                cy[i]=u;
                return 1;
            }
        }
    }
    return 0;
}

int Hopcroft_Karp()
{
    int ans=0;
    for(int i=1;i<=n;i++)
        cx[i]=-1;
    for(int i=1;i<=m;i++)
        cy[i]=-1;
    while(searchpath())
    { 
        for(int i=1;i<=m;i++)
            vis[i]=false;
        for(int i=1;i<=n;i++)
            if(cx[i]==-1)
                ans+=findpath(i);
    }
    return ans;
}
                                                                                                                                                                                      
int main()
{
    int x,y,k,icase=1;
    while(scanf(“%d%d%d”,&n,&m,&k))
    {
        if(n==0&&m==0&&k==0) break;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                map[i][j]=true;
        for(int i=1;i<=k;i++)
        {
            scanf(“%d%d”,&x,&y);
            map[x][y]=false;
        }
        printf(“Case %d: “,icase++);
        printf(“%d\n”,n+m-Hopcroft_Karp());
    }                                                                           
    return 0;
}


解题转自:http://blog.163.com/husanfeng_acm/blog/static/214534276201341611412327/


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  3. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  4. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?