PIGS POJ 1149 网络流

//以顾客为点，再添加超源点与超收点，如果顾客i是第一个打开j猪圈的，那么从超源点到顾客i有一条边，
//容量为猪圈j中猪的数目.如果出现重边，和合并，容量值相加。
//如果顾客i紧接着顾客j打开猪圈k,则顾客 i可以想顾客j连一条边，容量为正无穷
//从每个顾客向超收点连一条边，容量为每个顾客想买的猪的数目。
//这个网络流从0流开始增广

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #define MAXN 107 //顾客数
 4 #define MAXM 1007//猪圈数
 5 #define INF 300000000
 6 using namespace std;
 7 struct Acr
 8 {
 9     int c,f;  //容量和流量
10 } edge[MAXN][MAXN];//邻接矩阵存储边
11 int n,m;
12 void init()  //读入数据，构造出图
13 {
14     int ph[MAXM];//ph[i]表示i猪圈中猪的数目
15     int last[MAXM];//打开该猪圈的最后一位顾客的编号
16     int i,j;
17     memset(last,0,sizeof(last));
18     memset(edge,0,sizeof(edge));
19     scanf("%d%d",&m,&n);
20     for(i=1; i<=m; ++i)
21         scanf("%d",&ph[i]);
22     for(i=1; i<=n; ++i)
23     {
24         int num;
25         scanf("%d",&num);
26         for(j=0; j< num; ++j)
27         {
28             int key;
29             scanf("%d",&key);
30             if(last[key] == 0) edge[0][i].c += ph[key];  //打开该猪圈的第一个顾客，可买到的猪为猪圈中猪的数目
31             else
32                 edge[last[key]][i].c = INF;  //紧接着last[key]顾客打开该猪圈，相当于能从last[key]顾客那里买到尽可能多的猪
33             last[key] = i;   //顾客 i成为了最后打开 key猪圈的人
34         }
35         scanf("%d",&edge[i][n+1].c);  //每个顾客想要买的猪的数目就是每个顾客到超收点的边的容量值
36     }
37 }//其中，超源点编号为0，超收点编号为n+1.
38 void Ford()
39 {
40     int prev[MAXN];  //有边<u,v>,则会有prev[v] = u,存前一个顶点
41     int alpha[MAXN];//存可以增加的量
42     int queue[MAXN];//模拟BFS的队列
43     int i,j;
44     int t = n+1;
45     while(1)
46     {
47         memset(prev,0xff,sizeof(prev));//给所有顶点赋初值-1
48         int front=0,tail = 0;
49         queue[tail++] = 0;
50         alpha[0] = INF;
51         prev[0] = -2;
52         while(front != tail && prev[t] == -1)//BFS找一条增广路
53         {
54             int v= queue[front++];
55             for(i =0; i<=t ; ++i)
56             {
57                 int tmp ;
58                 if(prev[i] == -1 && (tmp = edge[v][i].c - edge[v][i].f ))//正负两种情况都包括了
59                 {
60                     prev[i] = v;
61                     alpha[i] = alpha[v] < tmp ? alpha[v]: tmp;
62                     queue[tail++] = i;
63                 }
64             }
65         }
66         if(prev[t] == -1) break;
67         for(i = prev[t],j =t; i != -2; j = i, i= prev[i])
68         {
69             edge[i][j].f += alpha[t];  //本来就是负的，就变正了，然后如果<u,v>中流量为f,可以认为<v,u>中流量为-f
70             edge[j][i].f = -edge[i][j].f;
71         }
72     }
73     int p;
74     for(i=1,p=0; i<t; ++i)
75         p += edge[i][t].f;
76     printf("%d\n",p);
77 }
78 int main()
79 {
80 //    freopen("in.cpp","r",stdin);
81     init();
82     Ford();
83     return 0;
84 }