学步园

题目 http://poj.org/problem?id=2289

这是我做的第一个 多重匹配   所以参考哦  别人代码   感觉不错

http://www.cnblogs.com/-sunshine/archive/2012/08/30/2664310.html

其实这个多重匹配有点像匈牙利算法   思想是一样的  

题意：给定一个规模为n的名单，要将名单中的人归到m个组中，给出每个人可能的分组号，需要确定一种分配方案，是的最大规模的组最小。

思路：一对多的二分图的多重匹配。二分图的多重匹配算法的实现类似于匈牙利算法，对于集合C中的元素xi，找到一个与其相连的元素yi后，检查匈牙利算法的两个条件是否成立，若yi未被匹配，则将
xi，yi匹配。否则，如果与yi匹配的元素已经达到上限，那么在所有与yi匹配的元素中选择一个元素，检查是否能找到一条增广路径，如果能，则让出位置，让xi与yi匹配。
二分求出limit，知道找到可以构成多重匹配的最小限制limit，在main函数中二分搜索。

ac代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define max 2001

bool map[max][max];
bool mark[max];
int link[max];
int cy[max][max];
int n,m,mid;   //n表示列表长度  m表示分配组数

bool findpath(int u)
{
    int i,j;
    for(i=0;i<m;i++)
    {
        if(map[u][i]&&!mark[i])
        {
            mark[i]=1;
            if(link[i]<mid)
            {
                cy[i][link[i]++]=u;
                return true;
            }
            for(j=0;j<link[i];j++)
            {
               if(findpath(cy[i][j]))
               {
                   cy[i][j]=u;
                   return true;
               }
            }
        }
    }
    return false;
}

bool maxmatch()
{
    int i,j;
    memset(link,0,sizeof(link));
    for(i=0;i<n;i++)
    {
        memset(mark,false,sizeof(mark));
        if(!findpath(i)) return false;

    }
    return true;
}

int main()
{
    int i,j,v;
    char len[1020];
    while(cin>>n>>m,n+m)
    {
        getchar();
        memset(map,false,sizeof(map));
       // memset(link,false,sizeof(link));

        for(i=0;i<n;i++)
        {
           cin.getline(len,1020);
           int k=strlen(len);

           for(j=0;j<=k;j++)
           {
               if(len[j]>='0'&&len[j]<='9')
               {
                     v=0;
                     while(len[j]>='0'&&len[j]<='9')
                     {
                         v=v*10+len[j++]-'0';
                     }
                     map[i][v]=1;
               }
           }
        }
        int left=0,right=n;
        while(left<right)
        {
            mid=(left+right)/2;
            if(maxmatch()) right=mid;
            else left=mid+1;
        }

        cout<<right<<endl;
    }
    return 0;
}