[poj 3281]最大流+建图很巧妙

题目链接：http://poj.org/problem?id=3281

看了kuangbin大佬的思路，还用着kuangbin板子orz   http://www.cnblogs.com/kuangbin/archive/2012/08/21/2649850.html

#include<cstdio>

#include<cstring>

using namespace std;

const int MAXN = ;

const int MAXM = ;

const int INF = 0x3f3f3f3f;

struct Edge

{

    int to,next,cap,flow;

} edge[MAXM];

int tol;

int head[MAXN];

int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];

void init()

{

    tol = ;

    memset(head,-,sizeof(head));

}

void addedge(int u,int v,int w,int rw=)

{

    edge[tol].to = v;

    edge[tol].cap = w;

    edge[tol].next = head[u];

    edge[tol].flow = ;

    head[u] = tol++;

    edge[tol].to = u;

    edge[tol].cap = rw;

    edge[tol].next = head[v];

    edge[tol].flow = ;

    head[v]=tol++;

}

int sap(int start,int end,int N)

{

    memset(gap,,sizeof(gap));

    memset(dep,,sizeof(dep));

    memcpy(cur,head,sizeof(head));

    int u = start;

    pre[u] = -;

    gap[] = N;

    int ans = ;

    while(dep[start] < N)

    {

        if(u == end)

        {

            int Min = INF;

            for(int i = pre[u]; i != -; i = pre[edge[i^].to])

                if(Min > edge[i].cap - edge[i].flow)

                    Min = edge[i].cap - edge[i].flow;

            for(int i = pre[u]; i != -; i = pre[edge[i^].to])

            {

                edge[i].flow += Min;

                edge[i^].flow -= Min;

            }

            u = start;

            ans += Min;

            continue;

        }

        bool flag = false;

        int v;

        for(int i = cur[u]; i != -; i = edge[i].next)

        {

            v = edge[i].to;

            if(edge[i].cap - edge[i].flow && dep[v]+ == dep[u])

            {

                flag = true;

                cur[u] = pre[v] = i;

                break;

            }

        }

        if(flag)

        {

            u = v;

            continue;

        }

        int Min = N;

        for(int i = head[u]; i != -; i = edge[i].next)

            if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)

            {

                Min = dep[edge[i].to];

                cur[u] = i;

            }

        gap[dep[u]]--;

        if(!gap[dep[u]])return ans;

        dep[u] = Min+;

        gap[dep[u]]++;

        if(u != start) u = edge[pre[u]^].to;

    }

    return ans;

}

int main()

{

    int n,F,D;

    scanf("%d%d%d",&n,&F,&D);

    init();

    for (int i=;i<n;i++) addedge(i,i+n,);

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

    {

        int f,d;

        scanf("%d%d",&f,&d);

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

        {

            int x;

            scanf("%d",&x);

            x--;

            addedge(n+n+x,i,);

        }

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

        {

            int x;

            scanf("%d",&x);

            x--;

            addedge(n+i,n+n+F+x,);

        }

    }

    for (int i=;i<F;i++) addedge(n+n+F+D,n+n+i,);

    for (int i=;i<D;i++) addedge(n+n+F+i,n+n+F+D+,);

    printf("%d",sap(n+n+F+D,n+n+F+D+,n+n+F+D+));

    return ;

}