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;

}