Description
有N个工作，M种机器，每种机器你可以租或者买过来. 每个工作包括若干道工序，每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。 现在给出这些参数，求最大利润
Solution
相对于最大权闭合子图,多了一个租用操作
实际上把中间的\(inf\)边改成租用的费用就可以了
这样要么割在\(S\)的出边,要么割在中间,要么割在\(T\)的入边了
分别对应舍弃这种物品的利润,租用和购买了
#include<bits/stdc++.h>
using namespace std;
const int N=2505,M=3000005,inf=2e8;
int n,m,T=N-1,S=0,head[N],nxt[M],to[M],dis[M],num=1;
inline void link(int x,int y,int z){nxt[++num]=head[x];to[num]=y;head[x]=num;dis[num]=z;nxt[++num]=head[y];to[num]=x;head[y]=num;dis[num]=0;
}
int dep[N];
inline bool bfs(){memset(dep,0,sizeof(dep));queue<int>q;q.push(S);dep[S]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=head[x];i;i=nxt[i]){int u=to[i];if(dis[i]<=0 || dep[u])continue;dep[u]=dep[x]+1;q.push(u);}}return dep[T];
}
inline int dfs(int x,int flow){if(x==T || !flow)return flow;int u,tot=0,t;for(int i=head[x];i;i=nxt[i]){u=to[i];if(dep[u]!=dep[x]+1 || dis[i]<=0)continue;t=dfs(u,min(flow,dis[i]));dis[i]-=t;dis[i^1]+=t;flow-=t;tot+=t;if(!flow)break;}if(!tot)dep[x]=-1;return tot;
}
inline int Dinic(){int t,tot=0;while(bfs()){t=dfs(S,inf);while(t)tot+=t,t=dfs(S,inf);}return tot;
}
int main(){freopen("pp.in","r",stdin);freopen("pp.out","w",stdout);scanf("%d%d",&n,&m);int x,y,cnt,tot=0;for(int i=1;i<=n;i++){scanf("%d%d",&x,&cnt);link(S,i,x);tot+=x;for(int j=1;j<=cnt;j++){scanf("%d%d",&x,&y);link(i,n+x,y);}}for(int i=1;i<=m;i++)scanf("%d",&x),link(i+n,T,x);printf("%d\n",tot-Dinic());return 0;
}