奶牛分配

奶牛分配(stall4.pas/in.out)

描述

农夫约翰上个星期刚刚建好了他的新牛棚，他使用了最新的挤奶技术。不幸的是，由于工程问题，每个牛栏都不一样。第一个星期，农夫约翰随便地让奶牛们进入牛栏，但是问题很快地显露出来：每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期，农夫约翰刚刚收集到了奶牛们的爱好的信息（每头奶牛喜欢在哪些牛栏产奶）。一个牛栏只能容纳一头奶牛，当然，一头奶牛只能在一个牛栏中产奶。

给出奶牛们的爱好的信息，计算最大分配方案。

输入格式

第一行 两个整数，N (0 <= N <= 200) 和 M (0 <= M <= 200) 。N 是农夫约翰的奶牛数量，M 是新牛棚的牛栏数量。

第二行到第N+1行 一共 N 行，每行对应一只奶牛。第一个数字 (Si) 是这头奶牛愿意在其中产奶的牛栏的数目 (0 <= Si <= M) 。后面的 Si 个数表示这些牛栏的编号。牛栏的编号限定在区间 (1..M) 中，在同一行，一个牛栏不会被列出两次。

输出格式

只有一行。输出一个整数，表示最多能分配到的牛栏的数量。

SAMPLE INPUT

5 5

2 2 5

3 2 3 4

2 1 5

3 1 2 5

1 2

SAMPLE OUTPUT

4

解法1：匈牙利算法

pre[1..m]记录每个牛棚里的奶牛，g[1..n][1..m]记录奶牛与喜欢的牛棚，f[i]记录i号牛棚是否被尝试匹配。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 200+10
using namespace std;

int n,m;
int pre[maxn];
bool g[maxn][maxn],f[maxn];

void init()
{
  freopen("stall4.in","r",stdin);
  freopen("stall4.out","w",stdout);
}

void readdata()
{
  memset(g,0,sizeof(g));
  
  scanf("%d%d",&n,&m);
  int i,si,j,k;
  for(i=1;i<=n;i++)
    {
      scanf("%d",&si);
      for(j=1;j<=si;j++)
        scanf("%d",&k),g[i][k]=1;
    }
}

bool find(int u)//尝试能否在不让已有牛棚奶牛无棚可住的情况下，u号奶牛能否匹配到牛棚
{
  int i;
  for(i=1;i<=m;i++)
    if(g[u][i] && !f[i])//若u号奶牛喜欢i号牛棚，且i号牛棚未尝试重新匹配
      {
        f[i]=1;
        if(pre[i]==0 || find(pre[i]))//若i号牛棚无主，则u号奶牛住i号牛棚；
          {pre[i]=u;return 1;}       //若i号牛棚有主，则尝试对i号牛棚的奶牛重匹配，若可行，i号牛棚就住u号牛
      }     
  return 0;
}

void work()
{
  int i,ans=0;
  for(i=1;i<=n;i++)
    {
      memset(f,0,sizeof(f));//每一次对i号奶牛进行匹配，用f[j]记录j号牛棚是否被尝试匹配过。
      if(find(i))ans++;
    }
  printf("%d\n",ans);  
}

int main()
{
  init();
  readdata();
  work();
  return 0;
}

</pre><pre class="cpp" name="code">解法二：最大流Sap

添加源点s=0，汇点ed=m+n+1，s到每个奶牛的流量为1，每个牛棚到ed的流量为1，

奶牛到喜爱牛棚的流量为1，否则为0，然后求解从s到ed的最大流，即为最大匹配数。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 400+10
using namespace std;

int n,m,ed;
int d[maxn],vd[maxn],g[maxn][maxn];

void init()
{
  freopen("stall4.in","r",stdin);
  freopen("stall4.out","w",stdout);
}

void chushi()
{
  memset(g,0,sizeof(g));
  memset(d,0,sizeof(int)*(ed+1));
  memset(vd+1,0,sizeof(int)*(ed));
  vd[0]=ed+1;
}

void readdata()
{
  scanf("%d%d",&n,&m);
  ed=n+m+1;  chushi();
  
  int i,j,si,k;
  for(i=1;i<=n;i++)
    {
      scanf("%d",&si);
      for(j=1;j<=si;j++)
        scanf("%d",&k),g[i][n+k]=1;
    }
  for(i=1;i<=n;i++)g[0][i]=1;
  for(i=n+1;i<=n+m;i++)g[i][ed]=1;  
}

int sap(int u,int flow)
{
  if(u==ed)return flow;
  
  int i,t,res=flow;
  for(i=1;i<=ed;i++)
    if(g[u][i]>0 && d[u]==d[i]+1)
      {
        t=sap(i,min(g[u][i],res));
        g[u][i]-=t;  g[i][u]+=t;
        if(!(res-=t))return flow;
      }
   if(d[0]<ed+1)
     {
       if(!(--vd[d[u]]))d[0]=ed+1;
       ++vd[++d[u]];
     }   
   return flow-res;  
}

void work()
{  
  int ans=0;
  for(;d[0]<ed+1;)
    ans+=sap(0,1000000000); 
  printf("%d\n",ans);  
}

int main()
{ 
  init();
  readdata();
  work();
  return 0;
}