【题目大意】
有F 种食物和D 种饮料，每种食物或饮料只能供一头牛享用，且每头牛只享用一
种食物和一种饮料。现在有 N 头牛，每头牛都有自己喜欢的食物种类列表和饮
料种类列表，问最多能使几头牛同时享用到自己喜欢的食物和饮料。（1 <= F <=
100, 1 <= D <= 100, 1 <= N <= 100）
【建模方法】
此题的建模方法比较有开创性。以往一般都是左边一个点集表示供应并与源相连，
右边一个点集表示需求并与汇相连。现在不同了，供应有两种资源，需求仍只有
一个群体，怎么办？其实只要仔细思考一下最大流的建模原理，此题的构图也不
是那么难想。最大流的正确性依赖于它的每一条s-t 流都与一种实际方案一一对
应。那么此题也需要用s-t 流将一头牛和它喜欢的食物和饮料“串”起来，而食
物和饮料之间没有直接的关系，自然就想到把牛放在中间，两边是食物和饮料，
由s, t 将它们串起来构成一种分配方案。至此建模的方法也就很明显了：每种食
物i 作为一个点并连边(s, i, 1)，每种饮料j 作为一个点并连边(j, t, 1)，将每头牛k
拆成两个点k’, k’’并连边(k’, k’’, 1), (i, k’, 1), (k’’, j, 1)，其中i, j 均是牛k 喜欢的食物
或饮料。求一次最大流即为结果。
#include<stdio.h>
#include<string.h>
const int EDGE_NUM = 20001;//边数
const int POINT_NUM = 501;//点数
struct edge
{
int v;//点
int next;//下一边
int value;//当前边流量
}edge[2*EDGE_NUM];//边信息，以邻接表形式存储
int p[POINT_NUM];//p[i]记录最后一条以i为起点的边的id,即以i为起点的最后一条边为edge[p[i]],而edge[p[i]].next则为以i为起点的倒数第二条边，以此类推
int level[POINT_NUM];//level[i]记录i点的层次
int que[POINT_NUM],out[POINT_NUM];//辅助数组
int edgeNumber;
void init()
{
edgeNumber = 0;
memset(p,-1,sizeof(p));
}
inline void addEdge(int from,int to,int value)//添加边，以邻接表形式存储
{
edge[edgeNumber].v = to;
edge[edgeNumber].value = value;
edge[edgeNumber].next = p[from];
p[from] = edgeNumber++;
}
int Dinic(int source,int sink,int n)
{
int i,maxFlow = 0;
while(true)
{
int head,tail;
for(i=0;i<n;i++)level[i] = 0;
level[source] = 1;//源点为第一层
head = 0;tail = 0;
que[0] = source;//que这里当队里使用
while(head<=tail)//BFS该剩余图，计算每个可达点层次
{
int cur = que[head++];
for(i=p[cur];i!=-1;i=edge[i].next)
{
if(edge[i].value>0&&level[edge[i].v]==0)
{
level[edge[i].v] = level[cur]+1;
que[++tail] = edge[i].v;
}
}
}
if(level[sink]==0)break;//不存在增广路
for(i=0;i<n;i++)out[i]=p[i];//out[i]动态记录可用边
int q = -1;//q为已经搜索到的点的个数,que存放途径边信息
while(true)//DFS剩余图，查找增广路
{
if(q<0)//当前路为空
{
int cur = out[source];
for(;cur!=-1;cur=edge[cur].next)//查找第一条边
{
if(edge[cur].value>0&&out[edge[cur].v]!=-1&&level[edge[cur].v]==2)//合法第一条边必须满足：1.流量大于0;2.终点有可用边 3:终点层次为2
break;
}
if(cur==-1)break;//找不到第二层，当前剩余图已经没有增广路
que[++q]=cur;//存入第一条边id
out[source]=edge[cur].next;
}
int curnode = edge[que[q]].v;//当前路的终点
if(curnode==sink)//找到一条增广路
{
int thisflow = edge[que[0]].value;//thisflow为当前增广路的流量
int index = 0;//标记最小流量边的id
for(i=1;i<=q;i++)
{
if(thisflow>edge[que[i]].value)
{
thisflow=edge[que[i]].value;
index = i;
}
}
maxFlow+=thisflow;
for(i=0;i<=q;i++)
{
edge[que[i]].value-=thisflow;
edge[que[i]^1].value+=thisflow;//与其方向相反的边
}
q = index-1;//查找下一条增广路时可直接使用当前路的前q条边
}
else//尚未找到汇点
{
int cur = out[curnode];
for(;cur!=-1;cur=edge[cur].next)
{
if(edge[cur].value>0&&out[edge[cur].v]!=-1&&level[edge[cur].v]==level[curnode]+1)
break;
}
if(cur==-1)//没有下一条路
{
out[curnode]=-1;//标记当前点的可达边为0
q--;
}
else
{
que[++q]=cur;
out[curnode]=edge[cur].next;//下一次搜索时可达边从edge[cur].next开始查找
}
}
}
}
return maxFlow;
}
int main()
{
int Nn,Ff,Dd;
while(scanf("%d%d%d",&Nn,&Ff,&Dd)!=EOF)
{
init();
int foodstart = 1;
int cow1 = Ff+2;
int cow2 = cow1+Nn+1;
int drinkstart = cow2+Nn+1;
int end = drinkstart+Dd+1;
int i;
for(i=0;i<Nn;i++)//添加牛边
{
addEdge(cow1+i,cow2+i,1);
addEdge(cow2+i,cow1+i,0);
}
for(i=0;i<Ff;i++)//添加食物边
{
addEdge(0,foodstart+i,1);
addEdge(foodstart+i,0,0);
}
for(i=0;i<Dd;i++)//添加饮料
{
addEdge(drinkstart+i,end,1);
addEdge(end,drinkstart+i,0);
}
for(i=0;i<Nn;i++)
{
int f,d;
scanf("%d%d",&f,&d);
int x;
while(f--)
{
scanf("%d",&x);
x--;
addEdge(foodstart+x,cow1+i,1);
addEdge(cow1+i,foodstart+x,0);
}
while(d--)
{
scanf("%d",&x);
x--;
addEdge(cow2+i,drinkstart+x,1);
addEdge(drinkstart+x,cow2+i,0);
}
}
printf("%d\n",Dinic(0,end,end+1));
}
return 0;
}
附上dinic模版
struct edge
{
int v, next;
int val;
} net[ 100010 ];
int level[maxn], Qu[maxn], out[maxn],next[maxn];
class Dinic {
public:
int end;
Dinic() {
end = 0;
memset( next, -1, sizeof(next) );
}
inline void insert( int x, int y, int c) {
net[end].v = y, net[end].val = c,
net[end].next = next[x],
next[x] = end ++;
net[end].v = x, net[end].val = 0,
net[end].next = next[y],
next[y] = end ++;
}
bool BFS( int S, int E ) {
memset( level, -1, sizeof(level) );
int low = 0, high = 1;
Qu[0] = S, level[S] = 0;
for( ; low < high; ) {
int x = Qu[low];
for( int i = next[x]; i != -1; i = net[i].next ) {
if( net[i].val == 0 ) continue;
int y = net[i].v;
if( level[y] == -1 ) {
level[y] = level[x] + 1;
Qu[ high ++] = y;
}
}
low ++;
}
return level[E] != -1;
}
int MaxFlow( int S, int E ){
int maxflow = 0;
for( ; BFS(S, E) ; ) {
memcpy( out, next, sizeof(out) );
int now = -1;
for( ;; ) {
if( now < 0 ) {
int cur = out[S];
for(; cur != -1 ; cur = net[cur].next )
if( net[cur].val && out[net[cur].v] != -1 && level[net[cur].v] == 1 )
break;
if( cur >= 0 ) Qu[ ++now ] = cur, out[S] = net[cur].next;
else break;
}
int u = net[ Qu[now] ].v;
if( u == E ) {
int flow = inf;
int index = -1;
for( int i = 0; i <= now; i ++ ) {
if( flow > net[ Qu[i] ].val )
flow = net[ Qu[i] ].val, index = i;
}
maxflow += flow;
for( int i = 0; i <= now; i ++ )
net[Qu[i]].val -= flow, net[Qu[i]^1].val += flow;
for( int i = 0; i <= now; i ++ ) {
if( net[ Qu[i] ].val == 0 ) {
now = index - 1;
break;
}
}
}
else{
int cur = out[u];
for(; cur != -1; cur = net[cur].next )
if (net[cur].val && out[net[cur].v] != -1 && level[u] + 1 == level[net[cur].v])
break;
if( cur != -1 )
Qu[++ now] = cur, out[u] = net[cur].next;
else out[u] = -1, now --;
}
}
}
return maxflow;
}
};