题目链接：http://poj.org/problem?id=3281
PS:刷够网络流了，先这样吧，之后再刷，慢慢补。
题意：有F种食物,D种饮料,N头奶牛,只能吃某种食物和饮料(而且只能吃特定的一份),一种食物被一头牛吃了之后,其余牛就不能吃了 第一行有N,F,D三个整数:接着2-N+1行代表第i头牛,前面两个整数是Fi与Di(食物与饮料的种类数量),接着是食物的种类与饮料的种类 要求输出最多分配能够满足的牛的数量.
思路：这是一种神奇的建图方式-拆点。让我想打死都想不出来。sad
建图,有2*n+f+d+2个顶点，0表示源点,2*n+f+d+1表示汇点。 由源点指向食物,再由食物指向牛,牛再指向对应的饮料,饮料再指向汇点 当然要使每一头牛都对应每一份食物与饮料,所以应该牛i指向牛i再指向饮料,这样就可以避免一头牛只占用多份食物与饮料了 全部是有向的边,而且权值全部为1 我在这里是1到f为食物点，f+1到f+2*n为牛点，f+2*n+1到f+2*n+d为饮料点
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <math.h>
#define N 1100
#define inf 0x3f3f3f3f
typedef int ll;
using namespace std;
ll n,f,d,tt,dis[N],head[N];
struct node
{
ll x,y,w,next;
} eg[N*N];
void init()
{
tt=;
memset(head,-,sizeof(head));
}
void add(int xx,int yy)
{
eg[tt].x=xx;
eg[tt].y=yy;
eg[tt].w=;
eg[tt].next=head[xx];
head[xx]=tt++;
eg[tt].x=yy;
eg[tt].y=xx;
eg[tt].w=;
eg[tt].next=head[yy];
head[yy]=tt++;
}
bool bfs(int s,int e)
{
memset(dis,-,sizeof(dis));
dis[s]=;
queue<int>q;
q.push(s);
while(!q.empty())
{
int fa=q.front();
q.pop();
for(int i=head[fa]; i!=-; i=eg[i].next)
{
int v=eg[i].y;
if(dis[v]==-&&eg[i].w)
{
dis[v]=dis[fa]+;
q.push(v);
}
}
}
if(dis[e]>)
return true;
return false;
}
int dinic(int s,int maxt)
{
if(s==*n+f+d+) return maxt;
int a,sum=maxt;
for(int i=head[s]; i!=-; i=eg[i].next)
{
int v=eg[i].y;
if(dis[v]==dis[s]+&&eg[i].w>)
{
a=dinic(v,min(sum,eg[i].w));
eg[i].w-=a;
eg[i+].w+=a;
sum-=a;
}
}
return maxt-sum;
}
int main()
{
ll xx,yy,s1,s2;
scanf("%d%d%d",&n,&f,&d); init();
for(int j=;j<=f;j++)
{
add(,j);
}
for(int j=;j<=d;j++)
{
add(f+*n+j,f+*n+d+);
}
for(int i=;i<=n;i++)
{
scanf("%d%d",&s1,&s2);
for(int j=;j<=s1;j++)
{
scanf("%d",&xx);
add(xx,f+i);
}
for(int j=;j<=s2;j++)
{
scanf("%d",&yy);
add(f+n+i,f+*n+yy);
}
}
for(int i=;i<=n;i++)
{
add(f+i,f+n+i);
}
ll ans=;
while(bfs(,*n+f+d+))
{
ans+=dinic(,inf);
}
printf("%d\n",ans); return ;
}