思路
思考这道题，直接用最大流难以解决问题，不妨换个思路。
我们将初始状态设为不计带这些下属所需费用情况下，带所有下属拍照方案赚取费用之和，设为 t。
对于每个方案，如果我们选择要带这些下属，那么就要从 t 中减去带这些下属要花的费用，如果我们选择不带这些下属，则需要减去这些下属带来的收益，即这些下属可以赚的费用。
现在，我们成功将原问题转化为求出最小的每个下属选或不选产生的代价，再用总拍照赚取费用 t 减去这个最小代价，这样即可求出我们想要的最大收益。
所有，原先的问题就被转换为最小割问题，具体可参考下方内容。
建图及实现
首先，建一个超级源点和一个超级汇点，将源点和所有方案连边，容量为方案产生的收益。
然后，将所有方案带他所需要带的下属连边，容量为无限。
最后，将每个下属和汇点连边，容量为带这个下属所需的费用。
最小割问题即是割掉一些边，使源点的水无法流到汇点，求割掉的边的最小容量。
根据最大流最小割定理，我们知道最小割等于最大流。
因为方案和下属之间的边容量为无限，所以最小割不可能割掉两者之间的边，被割掉的只能是源点与方案之间的边和下属与汇点之间的边，正好契合刚才的思路。当一遍最小割跑完之后，每个方案要么舍弃了赚取的收益，要么付出了赚取收益的代价，也就是带某些下属所需的费用。
解法显而易见，在图中跑一遍最大流，再用初始状态的总赚取费用减去即可。
AC code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
int m,n,s,t;
int ans=0;
int a[110],b[110];
struct Edge{
int to,net,val;
}e[300010];
int h[300010],tot=1;
int dis[300010],now[300010];
void add(int u,int v,int w)
{
e[++tot].to=v;
e[tot].net=h[u];
e[tot].val=w;
h[u]=tot;
}
bool bfs()
{
for(int i=0;i<=t;i++)
{
dis[i]=inf;
}
dis[s]=0;
queue<int> q;
q.push(s);
now[s]=h[s];
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=h[x];i;i=e[i].net)
{
int y=e[i].to;
if(e[i].val&&dis[y]inf)
{
dis[y]=dis[x]+1;
q.push(y);
now[y]=h[y];
if(yt) return 1;
}
}
}
return 0;
}
int dfs(int x,int flow)
{
if(x==t) return flow;
int k,res=0;
for(int i=now[x];i;i=e[i].net)
{
now[x]=i;
int y=e[i].to;
if(dis[y]dis[x]+1&&e[i].val)
{
k=dfs(y,min(flow,e[i].val));
e[i].val-=k;
e[i^1].val+=k;
res+=k;
flow-=k;
}
}
return res;
}
int main()
{
scanf("%d%d",&m,&n);
s=0,t=n+m+1;
int sum=0;
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
add(s,i,a[i]);
sum+=a[i];
int x;
while(scanf("%d",&x))
{
if(x0) break;
add(i,m+x,inf);
}
}
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
add(m+i,t,b[i]);
}
while(bfs())
{
ans+=dfs(s,inf);
}
printf("%d\n",sum-ans);
return 0;
}
