我是按照图论500题的文档来刷题的，看了这题怎么也不觉得这是最大流的题目。这应该是题目做得太少的缘故。

　　什么是最大流问题？最大流有什么特点？

　　最大流的特点我觉得有一下几点：

　　　　1、只有一个起点、一个终点。如果不是，我们可以构造超级源点，超级汇点。

　　　　2、边的容量有上限（有上下限的是另外一种特殊的最大流）。

　　　　3、最后求的是一个最大值。

　　这题可以找到一些影子，一头奶牛只能吃一种食物，喝一种饮料。如果只有一种限制我们能很快反应过来(二分最大匹配），但是两种限制就增加了难度。不过还是可以理解为对边的权值的限制，最后求最大值，就可以网最大流的方向去思考。

　　怎么建图成了解题的关键。怎么确定一头牛只吃一种食物，只喝一种饮料呢？一种食物被多头牛喜欢，一种饮料也被多头牛喜欢。比较如意理解的是多头牛想喝A饮料，就从这么多头牛（点）连边到A，然后A连一条边出去，边权是1，就决定了，A只能被一头牛选择。

　　具体的建图：

　　1、建立一个超级源点，向所有的食物（F个点）连权值都为1的边。超级源点假设是0。

　　2、从食物向牛连边，权值为1。食物被那头牛喜欢就连一条边。食物的编号为1~F。牛的编号是F+1 ~F+N。

　　3、牛向牛连边。可以理解为自己向自己连边，权值为1。但是编号不能相同。这就是拆点。这是很关键的一点。可以理解为有两个属性的一一对应，就是食物与饮料是一一对应的。前面的牛是F+1，与之对应的头的编号是F+1+N。

　　4、建立一个超级汇点，是所有的饮料都连向汇点。汇点编号为F+2*N+D+1。

 

我的代码在源点和汇点是有出入，源点S不是0，是F+2*N +D+1，汇点的 S+1。主要是SAP的模版习惯下标从1开始。

　

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N=410;const int M=2*N*N, INF=0x3f3f3f3f;struct node{    int to,next,w;}edge[M];int head[N],numh[N],h[N],cure[N],pre[N];int ans,tot;void SAP(int s, int e,int n){    int flow,u,tmp,neck,i;    ans=0;    for(i=1;i<=n;i++)        cure[i]=head[i];    numh[0]=n;    u=s;    while(h[s]
          
           edge[cure[i]].w)                {                    neck=i;                    flow =edge[cure[i]].w;                }            }            for(i=s;i!=e;i=edge[cure[i]].to)            {                tmp=cure[i];                edge[tmp].w-=flow;                edge[tmp^1].w+=flow;            }            ans+=flow;            u=neck;        }        for(i=cure[u];i!=-1;i=edge[i].next)            if(edge[i].w && h[u]==h[edge[i].to]+1) break;        if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;}        else        {            if(0==--numh[h[u]]) break; //GAP优化            cure[u]=head[u];            for(tmp=n,i=head[u];i!=-1;i=edge[i].next)                if(edge[i].w) tmp=min(tmp, h[edge[i].to]);            h[u]=tmp+1;            ++numh[h[u]];            if(u!=s) u=pre[u];        }    }}void init(){    tot=0;    memset(head,-1,sizeof(head));    memset(pre,-1,sizeof(pre));    memset(h,0,sizeof(h));    memset(numh,0,sizeof(numh));}void addedge(int i,int j,int w){    edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++;    edge[tot].to=i;edge[tot].w=0;edge[tot].next=head[j];head[j]=tot++;}int main(){    //freopen("test.txt","r",stdin);    int n,m,i,j,k,a,b,c,s,d,f;    while(scanf("%d%d%d",&a,&b,&c)!=EOF)    {        init();        // 1~b是食物编号，b+1 ~b+2a是牛的编号，b+2a+1 ~ b+2a+c是饮料的编号        s=2*a+b+c+1; n=2*a+b+c+2;        for(i=1;i<=b;i++) addedge(s,i,1);        for(i=1;i<=a;i++)        {            scanf("%d%d",&f,&d);            for(j=0;j