poj 1149(最大流,构图)

在网上看到一种很巧妙的构图方法，构图思路如下：

1.取超级源点和超级汇点；

2.当猪圈被第一次打开时，在源点与当前顾客之间连接一条边，容量为该猪圈的猪的头数；

3.当某个猪圈不是被第一次打开时，在上一个打开该猪圈的顾客与当前打开该猪圈的顾客之间连接一条边，容量为无穷大；

4.在每个顾客与汇点之间连接一条边，容量为该顾客要买猪的头数。

EK：

View Code

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 
 6 using namespace std;
 7 
 8 #define MAXN 105
 9 #define inf 0x7fffffff
10 #define Min(x,y) (x>y?y:x)
11 
12 int n,flow[MAXN][MAXN],maxflow,st,en,a[MAXN],cap[MAXN][MAXN],pre[MAXN];
13 int q[100000];
14 int EK()
15 {
16     memset(flow,0,sizeof(flow));
17     maxflow=0;
18     int head=0,tail=0;
19     while(1)
20     {
21         memset(a,0,sizeof(a));
22         a[st]=inf;
23         q[tail++]=st;
24         while(head<tail)
25         {
26             int u=q[head++];
27             for(int v=0;v<=n+1;v++)
28                 if(!a[v] && cap[u][v]>flow[u][v])
29                 {
30                     pre[v]=u;q[tail++]=v;
31                     a[v]=Min(a[u],cap[u][v]-flow[u][v]);
32                 }
33         }
34         if(a[en]==0) return maxflow;
35         for(int u=en;u!=st;u=pre[u])
36         {
37             flow[pre[u]][u]+=a[en];
38             flow[u][pre[u]]-=a[en];
39         }
40         maxflow+=a[en];
41     }
42 }
43 
44 int main()
45 {
46     int m;
47     int pig[1005];
48     int p[1005];
49     while(~scanf("%d%d",&m,&n))
50     {
51         for(int i=1;i<=m;i++)
52             scanf("%d",&pig[i]);
53         st=0,en=n+1;
54         memset(cap,0,sizeof(cap));
55         memset(p,0,sizeof(p));
56         for(int i=1;i<=n;i++)
57         {
58             int k,u;
59             scanf("%d",&k);
60             while(k--)
61             {
62                 scanf("%d",&u);
63                 if(!p[u]) cap[st][i]+=pig[u];
64                 else cap[p[u]][i]=inf;
65                 p[u]=i;
66             }
67             scanf("%d",&cap[i][en]);
68         }
69         printf("%d\n",EK());
70     }
71     return 0;
72 }

stl方便，但速度稍慢。