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
建图方式学习的其他人的，如下图（自己画的）
#include <stdio.h>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
const int max_n=1e5+10;
int pig[max_n],people[max_n];
int OUT,IN,num;
int h[max_n],pre[max_n];
int dis[max_n],flag[max_n];
struct Edge
{
int u,v;
int next,val;
}e[max_n];
void add_edge(int u,int v,int val)
{
e[num].u=u;
e[num].v=v;
e[num].val=val;
e[num].next=h[u];
h[u]=num++;
}
int BFS(int u)
{
memset(dis,-1,sizeof(dis));
queue <int> q;
q.push(u);
dis[u]=0;
while(!q.empty())
{
u=q.front();q.pop();
for(int i=h[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
if(dis[v]==-1&&e[i].val>0)
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
if(dis[IN]>=0) return 1;
return 0;
}
int dfs(int u,int f)
{
if(u==IN) return f;
if(f<=0) return 0;
int a;
for(int i=h[u];i!=-1;i=e[i].next)
{
int v=e[i].v;
if(dis[v]==dis[u]+1&&e[i].val>0&&(a=dfs(v,min(f,e[i].val))))
{
e[i].val-=a;
e[i^1].val+=a;
return a;
}
}
return 0;
}
int dinic()
{
int res=0;
int ans;//printf("******\n");
while(BFS(OUT))
{
while((ans=dfs(OUT,INF))) res+=ans;
}
return res;
}
int main()
{
int m,n;
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(h,-1,sizeof(h));
memset(pre,0,sizeof(pre));
memset(flag,0,sizeof(flag));
num=0;
IN=n+1;OUT=0;
for(int i=1;i<=m;i++) scanf("%d",&pig[i]);
for(int i=1;i<=n;i++)
{
int u,a,b;
scanf("%d",&a);
for(int j=0;j<a;j++)
{
scanf("%d",&u);
if(!pre[u])
{
if(!flag[i])
{
add_edge(OUT,i,pig[u]);
add_edge(i,OUT,0);
flag[i]=num-2;
}
else
{
e[flag[i]].val+=pig[u];
}
pre[u]=i;
}
else
{
add_edge(pre[u],i,INF);
add_edge(i,pre[u],0);
}
}
scanf("%d",&b);
add_edge(i,IN,b);
add_edge(IN,i,0);
}
int ret=dinic();
printf("%d\n",ret);
}
}
