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 6Sample Output
7——————————————————————————————————
题目大意：有N个顾客，有M个猪圈，每个猪圈有一定的猪，在开始的时候猪圈都是关闭的，顾客来买猪，顾客打开某个猪圈，可以在其中挑选一定的猪的数量，在这个顾客走后，可以在打开的猪圈中将某个猪圈的一些猪牵到另外一个打开的猪圈，然后所有的猪圈会关闭，这样下一个顾客来了继续上面的工作
现在求怎么一种方法，使所有顾客买的猪的总数最大
思路：猪圈数太大了，建边其实可以省略，直接把它的猪全部给第一个遇到的人，在记录下它的归属即可。建图源点和每个猪圈的第一个顾客连边，边的权是开始时猪圈中猪的数目，顾客j紧跟在顾客i之后打开某个猪圈，则边<i,j>的权是无限大每个顾客和汇点之间连边，边的权是顾客所希望购买的猪的数目
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <queue> #include <vector> #include <bitset> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; #define MAXN 500 struct node { int u, v, next, cap; } edge[MAXN*MAXN]; int nt[MAXN], s[MAXN], d[MAXN], visit[MAXN]; int cnt; int a[2005]; int b[2005]; void init() { cnt = 0; memset(s, -1, sizeof(s)); } void add(int u, int v, int c) { edge[cnt].u = u; edge[cnt].v = v; edge[cnt].cap = c; edge[cnt].next = s[u]; s[u] = cnt++; edge[cnt].u = v; edge[cnt].v = u; edge[cnt].cap = 0; edge[cnt].next = s[v]; s[v] = cnt++; } bool BFS(int ss, int ee) { memset(d, 0, sizeof d); d[ss] = 1; queue<int>q; q.push(ss); while (!q.empty()) { int pre = q.front(); q.pop(); for (int i = s[pre]; ~i; i = edge[i].next) { int v = edge[i].v; if (edge[i].cap > 0 && !d[v]) { d[v] = d[pre] + 1; q.push(v); } } } return d[ee]; } int DFS(int x, int exp, int ee) { if (x == ee||!exp) return exp; int temp,flow=0; for (int i = nt[x]; ~i ; i = edge[i].next, nt[x] = i) { int v = edge[i].v; if (d[v] == d[x] + 1&&(temp = (DFS(v, min(exp, edge[i].cap), ee))) > 0) { edge[i].cap -= temp; edge[i ^ 1].cap += temp; flow += temp; exp -= temp; if (!exp) break; } } if (!flow) d[x] = 0; return flow; } int Dinic_flow(int ss, int ee) { int ans = 0; while (BFS(ss, ee)) { for (int i = 0; i <= ee; i++) nt[i] = s[i]; ans+= DFS(ss, INF, ee); } return ans; } int main() { int n,m,u,v,c; while (~scanf("%d %d", &m, &n)) { init(); for(int i=1;i<=m;i++) scanf("%d",&a[i]); memset(b,0,sizeof b); for(int i=1; i<=n; i++) { scanf("%d",&m); for(int j=0;j<m;j++) { scanf("%d",&u); if(!b[u]) add(0,i,a[u]),b[u]=i; else add(b[u],i,INF); } scanf("%d",&u); add(i,n+1,u); } printf("%d\n",Dinic_flow(0,n+1)); } return 0; }
