思路

本题可转化为最大权闭合图问题。最大权闭合图是指在一个有向图中，对于图中的任意一个点，其所有出边指向的点都在该闭合图内，且该闭合图的权值之和最大。

1. 节点设置：

   • 设立一个源点 $S$ 和一个汇点 $T$。
   • $n$ 个工作对应图中的节点 $1$ 到 $n$。
   • $m$ 种机器对应图中的节点 $n+1$ 到 $n+m$。

2. 边的构建：

   • 从源点 $S$ 向每个工作节点连接一条边，边的容量为该工作的收入 $x_i$。
   • 从该工作节点向其需要的机器节点连接一条边，边的容量为租用该机器的费用 $b_{ij}$。
   • 从每个机器节点向汇点 $T$ 连接一条边，边的容量为购买该机器的费用 $y_i$。

最终输出总收益减去最小割（最大流），样例如下：

简单的来说，成本限制了最大流，保证了一定不会亏本，而当且仅当跑满最大流时，赚的最多（投的多，机器多，能做的项目多），最终用总共得到的钱减去成本就是赚的钱。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N=2500,M=5000000,INF=0x3f3f3f3f;
struct Edge{int to,cap,flow,ne;}e[M];
int he[N],cnt=0,cur[N],dep[N],S,T;
void addEdge(int u,int v,int cap){
	e[cnt]={v,cap,0,he[u]},he[u]=cnt++,
	e[cnt]={u,0,0,he[v]},he[v]=cnt++;
}
bool bfs(){
	memset(dep,-1,sizeof(dep));
	queue<int> q; q.push(S),dep[S]=0;
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int i=he[u];i!=-1;i=e[i].ne){
			int v=e[i].to;
			if(dep[v]==-1&&e[i].cap>e[i].flow)
				dep[v]=dep[u]+1,q.push(v);
		}
	}
	return dep[T]!=-1;
}
int dfs(int u,int f){
	if(u==T||f==0) return f;
	int flow=0;
	for(int &i=cur[u];i!=-1;i=e[i].ne){
		int v=e[i].to;
		if(dep[v]==dep[u]+1){
			int newf=dfs(v,min(f,e[i].cap-e[i].flow));
			if(newf>0){
				e[i].flow+=newf,e[i^1].flow-=newf,flow+=newf,f-=newf; // 边的编号要从 0 开始，head 要赋值为 -1。
				if(f==0) break;
			}
		}
	}
	return flow;
}
int dinic(){
	int maxFlow=0;
	while(bfs()){
		for(int i=S;i<=T;i++) cur[i]=he[i];
		maxFlow+=dfs(S,INF);
	}
	return maxFlow;
}
int main() {
	int n,m,h=0; cin>>n>>m; S=0,T=n+m+1;
	memset(he,-1,sizeof(he));
	for(int i=1,x,t;i<=n;i++) {
		cin>>x>>t,h+=x,addEdge(S,i,x);
		for(int j=0,a,b;j<t;j++)
			cin>>a>>b,addEdge(i,n+a,b);
	}
	for(int i=1,y;i<=m;i++) cin>>y,addEdge(n+i,T,y);
	cout<<h-dinic();
	return 0;
}