PIGS Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 20033 Accepted: 9179 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
代码
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; //标号法求矩阵网络最大流 const int maxn_N=105;//顶点 const int maxn_M=1005;//弧 const int INF=0x3f3f3f3f; int customer[maxn_N][maxn_N];//容量 int flow[maxn_M][maxn_M];//流量 int s,t;//源点和汇点 void init()//构图 { int M;//猪圈数量 int N;//顾客数量 int house[maxn_M];//初始数 int last[maxn_M];//回溯存路径 memset(last,0,sizeof(last)); memset(customer,0,sizeof(customer)); scanf("%d%d",&M,&N); s=0;//源点 t=N+1;//汇点 for(int i=1; i<=M; i++) scanf("%d",&house[i]); for(int i=1; i<=N; i++) { int num;//每个顾客拥有的钥匙数量 scanf("%d",&num); for(int j=0; j<num; j++) { int k;//钥匙序号 scanf("%d",&k); last[k]==0?customer[s][i]+=house[k]:customer[last[k]][i]=INF; last[k]=i; } scanf("%d",&customer[i][t]);//顾客到汇点，权值为顾客买猪数量 } // printf("*****\n"); } void ford()//标号法 { int prev[maxn_N];//回溯记录路径 int min_flow[maxn_N];//可改进量 int queue[maxn_M];//数组模拟队列 int q_star,q_end;//队列两头指针 int p;//cij-fij memset(flow,0,sizeof(flow));//初始流量为零流 min_flow[0]=INF;//源点的第二个分量无穷大 while(1)//标号然后增广，重复有限次可以退出循环 { for(int i=0; i<maxn_N; i++) prev[i]=-2; prev[0]=-1; q_star=q_end=0; queue[q_end++]=0;//源点入队 while(q_star<q_end&&prev[t]==-2) { int v=queue[q_star++]; for(int i=0; i<=t; i++) { if(prev[i]==-2&&(p=customer[v][i]-flow[v][i])) { prev[i]=v; queue[q_end++]=i; min_flow[i]=min(min_flow[v],p); } } } // printf("***\n"); if(prev[t]==-2)//没找到去汇点的增广路 break; for(int i=prev[t],j=t; i!=-1; j=i,i=prev[i]) { flow[i][j]+=min_flow[t]; flow[j][i]=-flow[i][j]; } } int sum=0; for(int i=0; i<t; i++) sum+=flow[i][t]; printf("%d\n",sum); } int main() { init(); ford(); return 0; }