这道题目关键是建图，图建完了算法都一样
这道题将每一个客户看做一个节点，并增加节点0，和节点n+1，节点0相当于网络的起点，节点n+1相当于网络的终点。
这道题将每一个客户看做一个节点，并增加节点0，和节点n+1，节点0相当于网络的起点，节点n+1相当于网络的终点。
每个客户都有打开每一个猪圈的钥匙，如果该客户是第一个打开该猪圈的，那么则将他和0相连，权值为猪圈里猪的数量，如果不是第一个打开的，则将他和最后一次打开那个猪圈的客户相连。最后，将客户和n+1相连，权值为他要购买的猪的数量，
PIGS
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 12293 | Accepted: 5437 |
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.
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.
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<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define mm(a) memset((a),0,sizeof((a)))
#define INF 0xFFFFFF
#define MAXN 110
#define MAXM 1010
int n,m,c[MAXN][MAXN],dis[MAXN],gap[MAXN];
int pig[MAXM];
int st,ed;
int sap(int u,int flow)
{
if(u==ed)
return flow;
int ans=0,i,t;
for(i=0;i<=n+1;++i)
if(c[u][i]&&dis[u]==dis[i]+1)
{
t=sap(i,min(flow-ans,c[u][i]));
c[u][i]-=t,c[i][u]+=t,ans+=t;
if(ans==flow)
return ans;
}
if(dis[st]>=n+2)
return ans;
if(!--gap[dis[u]]) //gap优化
dis[st]=n+2;
++gap[++dis[u]];
return ans;
}
void solve()
{
int ans=0;
int temp;
st=0,ed=n+1;
mm(c),mm(gap),mm(dis);
for(int i=1;i<=m;i++) scanf("%d",&pig[i]);
for(int i=1;i<=n;i++)
{
int nn;
scanf("%d",&nn);
for(int j=1;j<=nn;j++)
{
scanf("%d",&temp);
if(pig[temp]>=0)
{
c[0][i]+=pig[temp];
pig[temp]=-i;
}
else
{
c[-pig[temp]][i]=INF;
pig[temp]=-i;
}
}
scanf("%d",&temp);
c[i][n+1]=temp;
}
for(gap[0]=n+2;dis[st]<n+2;) ans+=sap(st,INF);
printf("%d\n",ans);
}
int main()
{
while(cin>>m>>n)
solve();
return 0;
}