题目描述
小B有n个下属，现小B要带着一些下属让别人拍照。
有m个人，每个人都愿意付给小B一定钱让n个人中的一些人进行合影。如果这一些人没带齐那么就不能拍照，小B也不会得到钱。
注意：带下属不是白带的！！！对于每个下属，如果他带了那么小B需要给他一些钱，保证当他拍照时配合。
请问，小B的净收益最多是多少。
输入输出格式
输入格式：
第1行有2个正整数m和n（0<m,n<=100）。接下来的m行，每行是一个要求拍照的人的有关数据。第一个数是他同意支付该合影的费用；接着是该合影需要的若干下属的编号，以一个0作为行的结束标记。最后一行的n个数是带每个下属的费用。
输出格式：
一个数，表示最大收益。小B可以一个人也不带。
输入输出样例
输入样例#1：
2 3
10 1 2 0
25 2 3 0
5 6 7
输出样例#1：
17
说明
对于10%的数据每个人都要求让全部n个人合影
对于30%的数据n<=15 m<=15
另有10%的数据答案为0
对于50%的数据n<=40 m<=40
另有10%的数据每个人只愿意拍一个人
对于100%的数据m,n<=100
思路：
裸网络流；
来，上代码：
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> #define maxn 205
#define INF 0x7fffffff using namespace std; struct EdgeType {
int v,f,e;
};
struct EdgeType edge[maxn*maxn*]; int n,m,ans,s,t=maxn-,head[maxn],deep[maxn],cnt=; char Cget; inline void in(int &now)
{
now=,Cget=getchar();
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
} inline void edge_add(int u,int v,int f)
{
edge[++cnt].v=v,edge[cnt].f=f,edge[cnt].e=head[u],head[u]=cnt;
edge[++cnt].v=u,edge[cnt].f=,edge[cnt].e=head[v],head[v]=cnt;
} bool bfs()
{
for(int i=s;i<=t;i++) deep[i]=-;
queue<int>que;que.push(s),deep[s]=;
while(!que.empty())
{
int now=que.front();que.pop();
for(int i=head[now];i;i=edge[i].e)
{
if(edge[i].f>&&deep[edge[i].v]<)
{
deep[edge[i].v]=deep[now]+;
if(edge[i].v==t) return true;
que.push(edge[i].v);
}
}
}
return false;
} int flowing(int now,int flow)
{
if(now==t||flow<=) return flow;
int oldflow=;
for(int i=head[now];i;i=edge[i].e)
{
if(edge[i].f<=||deep[edge[i].v]!=deep[now]+) continue;
int pos=flowing(edge[i].v,min(flow,edge[i].f));
if(pos>)
{
flow-=pos;
oldflow+=pos;
edge[i].f-=pos;
edge[i^].f+=pos;
if(flow==) return oldflow;
}
}
if(oldflow==) deep[now]=-;
return oldflow;
} int main()
{
in(m),in(n);
for(int i=;i<=m;i++)
{
int pos;
in(pos),ans+=pos;
edge_add(s,i,pos);
in(pos);
while(pos) edge_add(i,m+pos,INF),in(pos);
}
for(int i=;i<=n;i++)
{
int pos;in(pos);
edge_add(i+m,t,pos);
}
while(bfs()) ans-=flowing(s,INF);
printf("%d\n",ans);
return ;
}