poj3281

非常非常经典的构图

有二分图学习基础的话，很容易想到这是一个“三分图”的匹配问题

我们将牛，food，drink作为点

为了方便，我们将牛放在中间，每头牛的出边指向drink种类，入边由food指入

建立超级源点指向所有food，超级汇点指向所有drink，

要满足最多的牛，也就是求一个最大流

但注意，如果这样求最大流的话，会经过牛点不止一次（因为牛会有多个入边和多个出边）

所以我们考虑将牛点拆为两个点，中间流量为1，这样就能保证牛只经过1次了

 1 const max=1000007;
 2 var a:array[0..510,0..510] of longint;
 3     numh,h,cur,pre:array[0..1010] of longint;
 4     n,t,i,j,m,s,f,d,ans,x:longint;
 5 
 6 procedure sap;
 7   var i,j,flow,tmp,neck,u,k:longint;
 8   begin
 9     numh[0]:=0;
10     u:=0;
11     while h[0]<t+1 do
12     begin
13       if u=t then
14       begin
15         i:=0;
16         j:=cur[0];
17         flow:=max;
18         while i<>t do   //其实这个地方多余了，容易知道，瓶颈边的流量一定为1
19         begin
20           if flow>a[i,j] then
21           begin
22             neck:=i;
23             flow:=a[i,j];
24           end;
25           i:=j;
26           j:=cur[j];
27         end;
28         inc(ans,flow);
29         i:=0;
30         j:=cur[i];
31         while i<>t do
32         begin
33           dec(a[i,j],flow);
34           inc(a[j,i],flow);
35           i:=j;
36           j:=cur[i];
37         end;
38         u:=neck;
39       end;
40       k:=-1;
41       for i:=0 to t do
42         if (a[u,i]>0) and (h[u]=h[i]+1) then
43         begin
44           k:=i;
45           break;
46         end;
47       if k<>-1 then
48       begin
49         cur[u]:=k;
50         pre[k]:=u;
51         u:=k;
52       end
53       else begin
54         dec(numh[h[u]]);
55         if numh[h[u]]=0 then break;   //GAP优化
56         tmp:=t+1;
57         for i:=0 to t do
58           if (a[u,i]>0) then tmp:=min(tmp,h[i]);  //更新标号
59         h[u]:=tmp+1;
60         inc(numh[h[u]]);
61         if u<>0 then u:=pre[u];
62       end;
63     end;
64   end;
65 
66 begin
67   readln(n,m,s);
68   fillchar(a,sizeof(a),0);
69   t:=2*n+m+s+1;     //计算建图后总点数
70   for i:=1 to m do
71     a[0,2*n+i]:=1;
72   for i:=1 to s do
73     a[2*n+m+i,t]:=1;
74   for i:=1 to n do
75     a[i,i+n]:=1;
76   for i:=1 to n do
77   begin
78     read(f,d);
79     for j:=1 to f do
80     begin
81       read(x);
82       a[2*n+x,i]:=1;
83     end;
84     for j:=1 to d do
85     begin
86       read(x);
87       a[i+n,2*n+m+x]:=1;
88     end;
89   end;
90   fillchar(cur,sizeof(cur),255);
91   fillchar(pre,sizeof(pre),255);
92   fillchar(h,sizeof(h),0);
93   fillchar(numh,sizeof(numh),0);   
94   sap;
95   writeln(ans);
96 end.

View Code

这题带给我们两个启示：

拆点和建立超级源汇点是网络流构图的基础而又重要的部分
网络流的建图比较复杂（这题还算简单），要细心检查……；