题目大意

有$m$个项目和$n$个员工

做项目$i$可以获得$A_i$元，但是必须雇用若干个指定的员工。雇用员工$j$需要花费$B_j$元，且一旦雇用，员工$j$可以参加多个项目的开发

问经过合理的项目取舍,最多能挣多少钱

数据范围

$1\leqslant n,m \leqslant 100$

题解

如果每一个员工做一个项目都要重新付费，那么每个项目之间就独立了，贪心就可以解决

然而，每一个员工只需要雇佣一次，条件式的收益使得这道题有了最大权闭合子图的影子，事实上就是最大获利

所以就从源点向每一个项目连一条容量为$A_i$的边，从每一个项目向这个项目需要的每一位员工连一条容量为无限大的边，再从每一位员工向汇点连一条容量为$B_j$的边

设最小割为$ans$，则$result=\sum_{i=1}^{m}A_i-ans$

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
#define inf 0x3f3f3f3f
using namespace std;

struct edge{int to,next,c;}e[10050];
int d[205],last[205];
int n,m,ans,sum,s,t,et,p;
inline void addedge(int u,int v,int c){
        e[++et].to=v;e[et].c=c;e[et].next=last[u];last[u]=et;
        e[++et].to=u;e[et].c=0;e[et].next=last[v];last[v]=et;
}
inline int bfs(){
    memset(d,-1,sizeof(d));
    queue <int> q;q.push(s);d[s]=0;
    while(!q.empty()){
        int h=q.front();q.pop();
        goedge(i,h)
            if ((d[e[i].to]==-1)&&(e[i].c>0)){
                d[e[i].to]=d[h]+1;
                q.push(e[i].to);
            }
    }
    if (d[t]<0) return 0;
    return 1;
}
int dinic(int x,int flow){
    if (x==t) return flow;int a,used=0;
    goedge(i,x)
        if ((e[i].c>0)&&(d[e[i].to]==d[x]+1)){
            a=dinic(e[i].to,min(flow-used,e[i].c));
            e[i].c-=a;e[i^1].c+=a;used+=a;
            if (flow==used) return used;
        }
    if (!used) d[x]=-1;
    return used;
}
int main(){
        scanf("%d",&p);
        while(p--){
                scanf("%d%d",&m,&n);
                s=0;t=n+m+1;et=1;sum=ans=0;
                memset(last,0,sizeof(last));
                For(i,1,m){int a;scanf("%d",&a);addedge(s,i,a);sum+=a;}
                For(i,1,n){int a;scanf("%d",&a);addedge(i+m,t,a);}
                For(i,1,m){
                        int a;scanf("%d",&a);
                        For(j,1,a){int b;scanf("%d",&b);addedge(i,b+m+1,inf);}
                }
                while (bfs()) ans+=dinic(s,inf);
                printf("%d\n",sum-ans);
        }
        return 0;
}