# [POJ 1149] PIGS【网络流】

• 2018-01-20
• 0
• 0

## Problem:

 Time Limit: 1000MS Memory Limit: 10000K

Description

Mirko works on a pig farm that consists of M locked pig-houses and Mirko can't unlock any pighouse because he doesn't have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs.
All data concerning customers planning to visit the farm on that particular day are available to Mirko early in the morning so that he can make a sales-plan in order to maximize the number of pigs sold.
More precisely, the procedure is as following: the customer arrives, opens all pig-houses to which he has the key, Mirko sells a certain number of pigs from all the unlocked pig-houses to him, and, if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses.
An unlimited number of pigs can be placed in every pig-house.
Write a program that will find the maximum number of pigs that he can sell on that day.

Input

The first line of input contains two integers M and N, 1 <= M <= 1000, 1 <= N <= 100, number of pighouses and number of customers. Pig houses are numbered from 1 to M and customers are numbered from 1 to N.
The next line contains M integeres, for each pig-house initial number of pigs. The number of pigs in each pig-house is greater or equal to 0 and less or equal to 1000.
The next N lines contains records about the customers in the following form ( record about the i-th customer is written in the (i+2)-th line):
A K1 K2 ... KA B It means that this customer has key to the pig-houses marked with the numbers K1, K2, ..., KA (sorted nondecreasingly ) and that he wants to buy B pigs. Numbers A and B can be equal to 0.

Output

The first and only line of the output should contain the number of sold pigs.

Sample Input

```3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6```

Sample Output

`7`

Source

Croatia OI 2002 Final Exam - First day

## Solution: ## Code: O(N2E), E为总边数 [708K, 16MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int M, N;
int pig;
int prev;

struct Edge{
int np, flow, cap;
Edge *nxt, *rev;
};

struct Graph{
Edge *V, E;
int tope;

inline void addedge(int u, int v, int cap){
E[++tope].np = v, E[tope].flow = 0, E[tope].cap = cap;
E[tope].nxt = V[u], E[tope].rev = &E[tope + 1], V[u] = &E[tope];
E[++tope].np = u, E[tope].flow = 0, E[tope].cap = 0;
E[tope].nxt = V[v], E[tope].rev = &E[tope - 1], V[v] = &E[tope];
}
} G;

int lev;
Edge *arc;
int q, fr = 0, re = 0;

inline bool Dinic_BFS(){
memset(lev, -1, sizeof(lev));
fr = re = 0, q[re++] = 0, lev = 0;
while(fr != re){
int u = q[fr++];
for(register Edge *ne = G.V[u]; ne; ne = ne->nxt)
if(lev[ne->np] == -1 && ne->cap > ne->flow)
lev[ne->np] = lev[u] + 1, q[re++] = ne->np;
}
return lev > -1;
}

inline int Dinic_DFS(int u, int curflow){
if(u == 101) return curflow;
int remflow = curflow;
for(register Edge *ne = arc[u]; ne; ne = ne->nxt){
arc[u] = ne;
if(lev[ne->np] == lev[u] + 1 && ne->cap > ne->flow){
int dflow = Dinic_DFS(ne->np, min(remflow, ne->cap - ne->flow));
if(dflow){
ne->flow += dflow, ne->rev->flow -= dflow;
remflow -= dflow;
}
}
}
return curflow - remflow;
}

inline int Dinic(){
int maxflow = 0;
while(Dinic_BFS()){
for(register int i = 0; i <= 101; i++) arc[i] = G.V[i];
maxflow += Dinic_DFS(0, 0x3f3f3f3f);
}
return maxflow;
}

int main(){
scanf("%d%d", &M, &N);
for(register int i = 1; i <= M; i++) scanf("%d", pig + i);
for(register int i = 1; i <= N; i++){
int A, B, K;
scanf("%d", &A);
while(A--){
scanf("%d", &K);
prev[K] = i;
}
scanf("%d", &B);
}
int maxflow = Dinic();
printf("%d\n", maxflow);
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai