【最大流】【POJ1149】PIGS

【题目大意】 M个猪圈，每个猪圈里面有Mi头猪。有N个顾客要来买猪，每个人最大需求量Ni已知。每个顾客会指定打开哪几个猪圈，选择里面的猪购买。一开始猪圈都是关闭的，顾客打开之后，被打开的猪圈可以互相调换猪的数量，然后猪圈重新关闭。求最多卖出猪的数量。（1<=N<=100,1<=M<=1000）

【题目解析】（最大流）设立汇点T，将所有顾客节点连到汇点T，容量为顾客的最大需求。对于每个猪圈的第一个顾客，从源点S连有向边，容量为该猪圈猪的数量，如果有多条边连到同一个顾客，合并为一条，容量相加。然后是该猪圈的第i个顾客跟第i +１个顾客连有向边，容量为ＩＮＦ。

　　　　　　　建模分析 : 从顾客到汇点T的容量对应了顾客的最大需求量这一实际问题。“对于每个猪圈的第一个顾客，从源点S连有向边，容量为该猪圈猪的数量，如果有多条边连到同一个顾客，合并为一条，容量相加。”因此，从源点S到顾客的所有边上的总容量正好对应了所有猪圈猪的总数量。对于每个猪圈的第i个顾客和第i+1个顾客，表示第i个顾客选完之后可以轮到第i+1个顾客选择，另外一点，假设i打开了猪圈a和b，那么打开过猪圈a和b的人都会有边连到i上，因此i+1的来源就有a和b这2个猪圈，就能实现题目所说的“打开的猪圈可以互相调换猪的数量”这一条件。

【代码如下】

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <climits>
  4 #include <cstring>
  5 #include <vector>
  6 #include <deque>
  7 #include <algorithm>
  8 
  9 //#define FILE_IO
 10 
 11 using namespace std;
 12 
 13 const int Maxn = 1002, INF = INT_MAX;
 14 
 15 struct edge
 16 {
 17     int v, c;
 18     edge* next, * op;
 19     edge(int _v, int _c, edge* _next) : v(_v), c(_c), next(_next) {}
 20 }* E[Maxn], * Et[Maxn];
 21 
 22 int S, T, Maxflow, N, M, Pigs[1001], Able[101], Buy[101];
 23 vector <int> Lv, House[1001];
 24 deque <int> Q;
 25 
 26 void Init();
 27 inline void edgeAdd(int, int, int);
 28 void Dinic();
 29 bool Dinic_Label();
 30 int Dinic_Augment(int, int);
 31 void Print();
 32 
 33 
 34 int main()
 35 {
 36     #ifdef FILE_IO
 37     freopen("1149.in", "r", stdin);
 38     #endif
 39 
 40     Init();
 41     Dinic();
 42     Print();
 43 
 44     return 0;
 45 }
 46 
 47 void Init()
 48 {
 49     cin >> M >> N;
 50     S = 0; T = N + 1;
 51     for (int i = 1; i <= M; i ++) cin >> Pigs[i];
 52     for (int i = 1; i <= N; i ++)
 53     {
 54         int n; cin >> n;
 55         for (int j = 1; j <= n; j ++)
 56         {
 57             int y; cin >> y;
 58             if (House[y].empty())
 59             {
 60                 House[y].push_back(i);
 61                 Able[i] += Pigs[y];
 62             }
 63             else
 64             {
 65                 edgeAdd(House[y].back(), i, INF);
 66                 House[y].push_back(i);
 67             }
 68         }
 69         cin >> Buy[i];
 70     }
 71     for (int i = 1; i <= N; i ++)
 72         if (Able[i]) edgeAdd(S, i, Able[i]);
 73     for (int i = 1; i <= N; i ++) edgeAdd(i, T, Buy[i]);
 74 }
 75 
 76 inline void edgeAdd(int x, int y, int c)
 77 {
 78     E[x] = new edge(y, c, E[x]);
 79     E[y] = new edge(x, 0, E[y]);
 80     E[x] -> op = E[y]; E[y] -> op = E[x];
 81 }
 82 
 83 void Dinic()
 84 {
 85     while (Dinic_Label())
 86     {
 87         memcpy(Et, E, sizeof(Et));
 88         Maxflow += Dinic_Augment(S, INF);
 89     }
 90 }
 91 
 92 bool Dinic_Label()
 93 {
 94     Lv.assign(T + 1, -1); Lv[S] = 0;
 95     Q.clear(); Q.push_back(S);
 96     while (!Q.empty())
 97     {
 98         int i = Q.front(); Q.pop_front();
 99         for (edge* j = E[i]; j; j = j -> next)
100         {
101             if (j -> c && Lv[j -> v] == -1)
102             {
103                 Lv[j -> v] = Lv[i] + 1;
104                 if (j -> v == T) return true;
105                 Q.push_back(j -> v);
106             }
107         }
108     }
109     return false;
110 }
111 
112 int Dinic_Augment(int i, int bm)
113 {
114     if (i == T || bm == 0) return bm;
115     int iflow = 0;
116     for (edge* &j = Et[i]; j; j = j -> next)
117     {
118         if (j -> c && Lv[i] + 1 == Lv[j -> v])
119         {
120             int add = Dinic_Augment(j -> v, min(bm, j -> c));
121             j -> c -= add;
122             j -> op -> c += add;
123             iflow += add;
124             bm -= add;
125             if (bm == 0) break;
126         }
127     }
128     return iflow;
129 }
130 
131 void Print()
132 {
133     cout << Maxflow << endl;
134 }