FZU 1397 保送

网络流入门题。

源点到每一个学生连一条边，容量为1

每个学校到汇点连一条边，容量为L

符合要求的学生和学校之间连边，容量为1。

从源点到汇点的最大流就是答案。

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<map>

#include<queue>

#include<string>

#include<iostream>

#include<algorithm>

using namespace std;

int tot;

int A,B;

const int maxn = ;

const int INF = 0x7FFFFFFF;

struct Edge

{

    int from, to, cap, flow;

    Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f) {}

};

vector<Edge>edges;

vector<int>G[maxn];

bool vis[maxn];

int d[maxn];

int cur[maxn];

int n, m, s, t;

struct Stu

{

    vector<int>school;

    vector<int>flag;

}stu[];

struct Sch

{

    bool flag[+];

}h[];

map<string,int>zhuan;

void init()

{

    for (int i = ; i < maxn; i++) G[i].clear();

    edges.clear();

    s=;

    t=A+B+;

    tot=;

    zhuan.clear();

}

void AddEdge(int from, int to, int cap)

{

    edges.push_back(Edge(from, to, cap, ));

    edges.push_back(Edge(to, from, , ));

    int w = edges.size();

    G[from].push_back(w - );

    G[to].push_back(w - );

}

bool BFS()

{

    memset(vis, , sizeof(vis));

    queue<int>Q;

    Q.push(s);

    d[s] = ;

    vis[s] = ;

    while (!Q.empty())

    {

        int x = Q.front();

        Q.pop();

        for (int i = ; i<G[x].size(); i++)

        {

            Edge e = edges[G[x][i]];

            if (!vis[e.to] && e.cap>e.flow)

            {

                vis[e.to] = ;

                d[e.to] = d[x] + ;

                Q.push(e.to);

            }

        }

    }

    return vis[t];

}

int DFS(int x, int a)

{

    if (x == t || a == )

        return a;

    int flow = , f;

    for (int &i = cur[x]; i<G[x].size(); i++)

    {

        Edge e = edges[G[x][i]];

        if (d[x]+ == d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>)

        {

            edges[G[x][i]].flow+=f;

            edges[G[x][i] ^ ].flow-=f;

            flow+=f;

            a-=f;

            if(a==) break;

        }

    }

    if(!flow) d[x] = -;

    return flow;

}

int dinic(int s, int t)

{

    int flow = ;

    while (BFS())

    {

        memset(cur, , sizeof(cur));

        flow += DFS(s, INF);

    }

    return flow;

}

int main()

{

    while(~scanf("%d%d",&A,&B))

    {

        if(!A&&!B) break;

        init();

        for(int i=;i<=A;i++) AddEdge(s,i,);

        for(int i=;i<=A;i++)

        {

            int d,p; scanf("%d%d",&d,&p);

            stu[i].flag.clear();

            stu[i].school.clear();

            for(int j=;j<=d;j++)

            {

                string name; cin>>name;

                if(zhuan[name]==) {zhuan[name]=tot;tot++;}

                stu[i].flag.push_back(zhuan[name]);

            }

            for(int j=;j<=p;j++)

            {

                int x; scanf("%d",&x);

                stu[i].school.push_back(x);

            }

        }

        for(int i=;i<=B;i++)

        {

            int L,F;scanf("%d%d",&L,&F);

            AddEdge(i+A,t,L);

            memset(h[i].flag,,sizeof h[i].flag);

            for(int j=;j<=F;j++)

            {

                string name; cin>>name;

                if(zhuan[name]==) {zhuan[name]=tot;tot++;}

                h[i].flag[zhuan[name]]=;

            }

        }

        for(int i=;i<=A;i++)

        {

            for(int j=;j<stu[i].school.size();j++)

            {

                int xue=stu[i].school[j];

                for(int k=;k<stu[i].flag.size();k++)

                    if(h[xue].flag[stu[i].flag[k]])

                        AddEdge(i,A+xue,);

            }

        }

        printf("%d\n",dinic(s,t));

    }

    return ;

}