|
PIGS
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 |
题意：略，注意两点：1.顾客是一个接一个来, 2.来了买了猪以后就马上锁上了猪房。
思路：网络流，重在构图。将每个顾客当做一个节点来表示，再加入超级源点和超级汇点。
1. 对于每个猪圈的第一个顾客，从源点向他连一条边，容量为猪圈里的猪的数量。
2. 对于每个猪圈，如果不是第一个顾客，则上一个打开这个猪圈的顾客向这个顾客连一条边，容量为 +∞。
3. 每个顾客到汇点连一条边，容量为各个顾客能买的数量。
建立一个源点,向每个猪舍连一条边,边容量为猪舍的初始容量;
建立一个汇点,由每个顾客向汇点连接一条边,边容量为每个顾客要买的猪的数目
在每个顾客和要打开的猪舍之间连一条边
如果问题是所有顾客同时选择并且不同的猪舍之间没有流动的话那么这么建图是可以的,但这道题每个顾客挑选是有先后顺序的,并且在打开的猪舍之间允许流通,所以要对上述模型进行修改
很显然的问题是一个猪舍用一个点来表示表达能力太弱了,因为我们不仅要知道每个猪舍猪的初始数量,还要在购买过程中维护每个猪舍的的数量,
对购买过程中的每个猪舍,
这个猪舍猪的来源有:上一次购买之后从其他打开的猪舍流动过来的,上一次购买之后本猪舍自己剩下的;
这个猪舍的猪的去向有:留在本猪舍,流向其他猪舍,被顾客买走
所以这道题要用到拆点的手段,将一个猪舍拆分成多个与购买过程对应的点,这么一来就可以处理顾客购买的先后问题以及猪舍之间的流动问题, 但是这种方式要建立的点的数目太多了,所以实际建图时要通过合并边和合并点来简化构图,所以这道题还是比较有难度的一道题,但是也是一道经典的题目
简化之后的建图方式如下:
• 每个顾客分别用一个结点来表示。
• 对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的猪的初始数量。如果从源点到一名顾客有多条边，则可以把它们合并成一条，容量相加。
• 对于每个猪圈，假设有n个顾客打开过它，则对所有整数i∈[1, n)，从该猪圈的第i个顾客向第i + 1个顾客连一条边，容量为∞。
• 从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。
• 对于每个猪圈的第一个顾客，从源点向他连一条边，容量就是该猪圈里的猪的初始数量。如果从源点到一名顾客有多条边，则可以把它们合并成一条，容量相加。
• 对于每个猪圈，假设有n个顾客打开过它，则对所有整数i∈[1, n)，从该猪圈的第i个顾客向第i + 1个顾客连一条边，容量为∞。
• 从各个顾客到汇点各有一条边，容量是各个顾客能买的数量上限。
这么建图,顶点数最多有102个,所以是完全可行的
这道题的经典之处在于建图之后的优化
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int VM=1010; const int INF=0x3f3f3f3f; int m,n,src,des; int g[VM][VM],dep[VM],pig[VM],house[VM]; int BFS(){ queue<int> q; while(!q.empty()) q.pop(); memset(dep,-1,sizeof(dep)); dep[src]=0; q.push(src); while(!q.empty()){ int u=q.front(); q.pop(); for(int v=src;v<=des;v++) if(g[u][v]>0 && dep[v]==-1){ dep[v]=dep[u]+1; q.push(v); } } return dep[des]!=-1; } int DFS(int u,int minx){ if(u==des) return minx; int tmp; for(int v=src;v<=des;v++) if(g[u][v]>0 && dep[v]==dep[u]+1 && (tmp=DFS(v,min(minx,g[u][v])))){ g[u][v]-=tmp; g[v][u]+=tmp; return tmp; } return 0; } int Dinic(){ int ans=0,tmp; while(BFS()){ while(1){ tmp=DFS(src,INF); if(tmp==0) break; ans+=tmp; } } return ans; } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d%d",&m,&n)){ memset(house,0,sizeof(house)); memset(g,0,sizeof(g)); src=0, des=n+1; for(int i=1;i<=m;i++) scanf("%d",&pig[i]); int num,k; for(int i=1;i<=n;i++){ scanf("%d",&num); while(num--){ scanf("%d",&k); if(!house[k]) // 第k猪圈的第一个顾客，从源点向他连一条边 g[src][i]+=pig[k]; else g[house[k]][i]=INF; // 不是第一个顾客，上一个开这个猪圈的顾客向他连一条边。 house[k]=i; // 维护come[k] } scanf("%d",&g[i][des]); // 每个客户连到汇点的边 } printf("%d\n",Dinic()); } return 0; }
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 6 using namespace std; 7 8 const int maxn=1010; 9 const int INF=0x3f3f3f3f; 10 11 int map[110][110]; 12 int pre[110],vis[110]; 13 int pig[maxn],come[maxn]; 14 int n,m,ans,s,t; // 源点为s，汇点为t。 15 16 int BFS(){ 17 queue<int> q; 18 while(!q.empty()) 19 q.pop(); 20 memset(pre,-1,sizeof(pre)); 21 memset(vis,0,sizeof(vis)); 22 q.push(s); // 加入源点。 23 pre[s]=0; 24 vis[s]=1; 25 int cur; 26 while(!q.empty()){ 27 cur=q.front(); 28 q.pop(); 29 for(int i=s;i<=t;i++) 30 if(!vis[i] && map[cur][i]){ 31 vis[i]=1; 32 q.push(i); 33 pre[i]=cur; 34 if(i==t) // 到达汇点。 35 return 1; 36 } 37 } 38 return 0; 39 } 40 41 void EK(){ 42 int tmp; 43 while(BFS()){ 44 tmp=INF; 45 for(int i=t;i!=s;i=pre[i]) // 从汇点t开始，利用pre[]回溯，直到找到源点s。 46 tmp=min(tmp,map[pre[i]][i]); 47 for(int i=t;i!=s;i=pre[i]){ 48 map[pre[i]][i]-=tmp; 49 map[i][pre[i]]+=tmp; 50 } 51 ans+=tmp; 52 } 53 } 54 55 int main(){ 56 57 //freopen("input.txt","r",stdin); 58 59 while(~scanf("%d%d",&m,&n)){ 60 s=0,t=n+1; 61 memset(come,0,sizeof(come)); 62 memset(map,0,sizeof(map)); 63 for(int i=1;i<=m;i++) 64 scanf("%d",&pig[i]); 65 int num,k; 66 for(int i=1;i<=n;i++){ 67 scanf("%d",&num); 68 while(num--){ 69 scanf("%d",&k); 70 if(!come[k]) // 第k猪圈的第一个顾客，从源点向他连一条边 71 map[s][i]+=pig[k]; 72 else // 不是第一个顾客，上一个开这个猪圈的顾客向他连一条边。 73 map[come[k]][i]=INF; 74 come[k]=i; // 维护come[k] 75 } 76 cin>>map[i][t]; // 每个客户连到汇点的边 77 } 78 ans=0; 79 EK(); 80 printf("%d\n",ans); 81 } 82 return 0; 83 }