题意：有一个养猪场，厂长没有钥匙，这个养猪场一共M个猪圈，N个顾客，每个顾客有一些猪圈的钥匙，每个顾客需要一些猪，问你厂长最多能卖多少猪？这里有个条件是，厂长可以在一个顾客买完后，调整没有锁门的猪圈中猪数量，比如，把几个猪圈中的猪全部转到一个猪圈内（这个条件会影响到后期建图），然后再关门，等下一个顾客；
解题思路：因为这里猪圈猪的数量限制的是顾客能买的数量，所以把顾客当成结点建图：
首先，设立一个源点，这个点与每个猪圈的第一个顾客相连接，代表流入的流量
然后每两个可以直接相连的顾客的容量设为无限大，因为我可以在上一个顾客买完后，把附近几个猪圈的猪尽量集中到下一个顾客能开门的猪圈中（这里直接相连的意思就是钥匙有重复），，所以下一个顾客流入尽可能多的流量，所以把容量设成无限大；
最后，每个顾客结点和汇点相连，容量为每个顾客自己需要猪的数量；
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define maxn 200005
#define inf 0x3f3f3f3f
using namespace std;
struct Edge
{
int next;
int to;
int w;
}edge[maxn];
int cnt;
int head[maxn];
int cur[maxn];
int depth[maxn];
int belong[maxn];
int a[maxn];
int s,e,n,m;
void add(int u,int v,int w)
{
edge[cnt].next=head[u];edge[cnt].w=w;
edge[cnt].to=v;head[u]=cnt++;
edge[cnt].next=head[v];edge[cnt].w=0;
edge[cnt].to=u;head[v]=cnt++;
}
bool bfs()
{
memset(depth,0,sizeof(depth));
depth[s]=1;
queue<int>que;que.push(s);
while(!que.empty())
{
int u=que.front();que.pop();
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(!depth[v]&&edge[i].w>0)
{
depth[v]=depth[u]+1;que.push(v);
}
}
}
return depth[e];
}
int dfs(int u,int maxflow)
{
int tempflow;
if(u==e)
return maxflow;
int add=0;
for(int &i=cur[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(depth[v]==depth[u]+1&&edge[i].w>0&&(tempflow=dfs(v,min(maxflow-add,edge[i].w))))
{
edge[i].w-=tempflow;
edge[i^1].w+=tempflow;
add+=tempflow;
if(maxflow==add)
break;
}
}
return add;
}
int dinic()
{
int ans=0;
while(bfs())
{
for(int i=0;i<=2*n;i++)
cur[i]=head[i];
while(int temp=dfs(s,inf))
ans+=temp;
}
return ans;
}
int main()
{
int x,y,w;
int k;
int d;
scanf("%d%d",&m,&n);
s=0;e=n+1;
memset(head,-1,sizeof(head));
cnt=0;
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&k);
y=0;
for(int j=1;j<=k;j++)
{
scanf("%d",&x);
if(belong[x]==0)
{
y+=a[x];
}
else
{
add(belong[x],i,inf);
}
belong[x]=i;
}
add(s,i,y);
scanf("%d",&d);
add(i,e,d);
}
printf("%d
",dinic());
}