FZU 1397 保送

Description

吉林一中是一所远近闻名的学校。每年都会有一些学生被保送到全国各个大学就读。最近，2006年的保送工作即将展开。 今年有N个人具有保送的资格(至少要在某些科目上获奖)，并且有M个学校想要在吉林一中招收保送生。由于人数限制，每个学校都有他们的招收上限，而且在每个学生的心里也有他们理想的大学。 每个学校都有他们喜欢的科目，所以他们只招收在符合他们要求的科目上获奖的学生。 我们想要知道，最多可以有多少的学生可以同时保送。

Input

输入包含多组测试数据。每组数据的第一行包含两个整数N, M, (1<= N <= 300, 1<= M <= 300), N表示学生总数，M表示大学总数。学生被编号为1到N，学校被编号为1到M。 接下来N行，每行描述一个学生，首先有两个整数d p, d 是该学生获奖总数，p是学生理想的大学的数目，然后d个单词，表示该学生获奖科目。然后p个数字表示该学生理想的大学编号。 接下来M行，每行描述一个学校，首先有两个整数l f，l是该学校招收的最多人数，接下来f个单词表示该学校招收的获奖科目。 输入文件结束于 N = M = 0。

Output

对于每组数据，输出包含一个整数即为最多可以同时保送的人数。

Sample Input

3 3

1 1 math 1

1 1 math 2

1 1 physics 3

2 1 math

2 1 math

2 2 math physics

0 0

Sample Output

3

裸的网络最大流，关键在于把图给建出来。

#include<cstdio>
#include<cmath>
#include<map>
#include<string>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e3+10;
int n,m,x,y,z;
char ss[maxn];
vector<string> s[maxn];
vector<int> t[maxn];
map<string,bool> M[maxn];
int v[maxn];

struct MaxFlow
{
  const static int maxe = 2e5 + 10;    //边数
  const static int maxp = 1e3 + 10;   //点数
  const static int INF = 0x7FFFFFFF;
  struct Edges
  {
    int x, f;
    Edges(){}
    Edges(int x, int f) :x(x), f(f){}
  }edge[maxe];
  int first[maxp], next[maxe], dis[maxp], tot, work[maxp], n;

  void clear(int x){ n = x; tot = 0; for (int i = 0; i <= n; i++) first[i] = -1; }

  void AddEdge(int s, int t, int f)
  {
    edge[tot] = Edges(t, 0); next[tot] = first[s]; first[s] = tot++;
    edge[tot] = Edges(s, f); next[tot] = first[t]; first[t] = tot++;
  }

  bool bfs(int s, int t)
  {
    for (int i = 0; i <= n; i++) dis[i] = -1;
    queue<int> p;    p.push(s);    dis[s] = 0;
    while (!p.empty())
    {
      int q = p.front();    p.pop();
      for (int i = first[q]; i != -1; i = next[i])
      {
        if (edge[i ^ 1].f&&dis[edge[i].x] == -1)
        {
          p.push(edge[i].x);
          dis[edge[i].x] = dis[q] + 1;
          if (dis[t] != -1) return true;
        }
      }
    }
    return false;
  }

  int dfs(int s, int t, int low)
  {
    if (s == t) return low;
    for (int &i = work[s], x; i >= 0; i = next[i])
    {
      if (dis[s] + 1 == dis[edge[i].x] && edge[i ^ 1].f && (x = dfs(edge[i].x, t, min(low, edge[i ^ 1].f))))
      {
        edge[i].f += x;    edge[i ^ 1].f -= x;  return x;
      }
    }
    return 0;
  }

  int dinic(int s, int t)
  {
    int maxflow = 0, inc = 0;
    while (bfs(s, t))
    {
      for (int i = 0; i <= n; i++) work[i] = first[i];
      while (inc = dfs(s, t, INF)) maxflow += inc;
    }
    return maxflow;
  }
}solve;

int main()
{
  while (~scanf("%d%d",&n,&m),n+m) 
  {
    for (int i=1;i<=n;i++)
    {
      scanf("%d%d",&x,&y);
      t[i].clear(); s[i].clear();
      while (x--) scanf("%s",ss),s[i].push_back(ss);
      while (y--) scanf("%d",&z),t[i].push_back(z);
    }
    solve.clear(n+m+1);
    for (int i=1;i<=m;i++)
    {
      scanf("%d%d",&v[i],&x); M[i].clear();
      while (x--) scanf("%s",ss),M[i][ss]=true;
      solve.AddEdge(i+n,m+n+1,v[i]);
    }
    for (int i=1;i<=n;i++)
    {
      solve.AddEdge(0,i,1);
      for (int j=0;j<t[i].size();j++)
      {
        for (int k=0;k<s[i].size();k++)
        {
          if (M[t[i][j]][s[i][k]])
          {
            solve.AddEdge(i,t[i][j]+n,1);
            break;
          }
        }
      }
    }
    printf("%d\n",solve.dinic(0,n+m+1));
  }
  return 0;
}