题意:
有N个工作,M种机器,每种机器你可以租或者买过来. 每个工作包括若干道工序,每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。 现在给出这些参数,求最大利润
题解:
网络流最大权闭合子图模型。
最大权闭合子图模型的答案通解为所有收益-最小割。
这道题因为加入了租用,与普通建图略有区别。
考虑存在的三条流:
- S->项目
- 项目->机器
- 机器->T
这个图的最小割一定会割掉以上三条之一,割掉1)是放弃项目,割掉2)是使用机器,割掉3)是购买机器,所以我们只需要将2中的流量设为租借费用即可。
参考代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int inf=0x3f3f3f3f;
const int MAXN=3000;
const int MAXM=2e6;
struct node
{
int v,w,nxt;
} edge[MAXM*2];
int n,m,cnt,st,ed;
int fir[MAXN],depth[MAXN],cur[MAXN];
void addedge(int u,int v,int w)
{
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].nxt=fir[u];
fir[u]=cnt++;
}
int dfs(int u,int flow)
{
if(u==ed)
return flow;
for(int &i=cur[u]; i!=-1; i=edge[i].nxt)
{
int v=edge[i].v;
int w=edge[i].w;
if(depth[v]==depth[u]+1&&w!=0)
{
int di=dfs(v,min(flow,w));
if(di>0)
{
edge[i].w-=di;
edge[i^1].w+=di;
return di;
}
}
}
return 0;
}
bool bfs()
{
queue<int> q;
while(!q.empty())
q.pop();
memset(depth,0,sizeof(depth));
depth[st]=1;
q.push(st);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=fir[u]; i!=-1; i=edge[i].nxt)
{
int v=edge[i].v;
int w=edge[i].w;
if(depth[v]==0&&w>0)
{
depth[v]=depth[u]+1;
q.push(v);
}
}
}
if(depth[ed]>0)
return 1;
else
return 0;
}
int dinic()
{
int tot=0;
while(bfs())
{
for(int i=0; i<=n+m+1; i++)
cur[i]=fir[i];
while(int temp=dfs(st,inf))
tot+=temp;
}
return tot;
}
int main()
{
scanf("%d%d",&n,&m);
int sum=0;
memset(fir,-1,sizeof(fir));
for(int i=1;i<=n;i++)
{
int w1,num;
scanf("%d%d",&w1,&num);
sum+=w1;
addedge(0,i,w1);
addedge(i,0,0);
for(int j=1;j<=num;j++)
{
int id,w2;
scanf("%d%d",&id,&w2);
addedge(i,id+n,w2);
addedge(id+n,i,0);
}
}
for(int i=1;i<=m;i++)
{
int w3;
scanf("%d",&w3);
addedge(i+n,n+m+1,w3);
addedge(n+m+1,i+n,0);
}
st=0; ed=n+m+1;
int ans=sum-dinic();
printf("%d\n",ans);
return 0;
}