[POJ 1149] PIGS【网络流】

  • 2018-01-20
  • 0
  • 0


Time Limit: 1000MS Memory Limit: 10000K


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.


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.


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



Croatia OI 2002 Final Exam - First day





同时,由于允许调动,后到的顾客若和先到的顾客有同一个猪圈的钥匙,就可以购买先到的顾客所剩下的所有猪,所以我们可以类比链表的思想,从拥有同一猪圈钥匙的前一个顾客到后一个顾客连一条容量为 的边。

建图完毕后跑 Dinic 算出最大流即为答案。

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

using namespace std;

int M, N;
int pig[1005];
int prev[1005];

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

struct Graph{
	Edge *V[105], E[10005];
	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[102];
Edge *arc[102];
int q[102], fr = 0, re = 0;

inline bool Dinic_BFS(){
	memset(lev, -1, sizeof(lev));
	fr = re = 0, q[re++] = 0, lev[0] = 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[101] > -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));
				ne->flow += dflow, ne->rev->flow -= dflow;
				remflow -= dflow;
	return curflow - remflow;

inline int Dinic(){
	int maxflow = 0;
		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);
			scanf("%d", &K);
			if(!prev[K]) G.addedge(0, i, pig[K]);
			else G.addedge(prev[K], i, 0x3f3f3f3f);
			prev[K] = i;
		scanf("%d", &B);
		G.addedge(i, 101, B);
	int maxflow = Dinic();
	printf("%d\n", maxflow);
	return 0;





OPEN AT 2017.12.10

If the code cannot be displayed normally, please refresh the page.


- Theme by Qzhai