题目链接：BZOJ1391-CEOI2008-Order

题意：

有N个工作，M种机器，每种机器你可以租或者买过来. 每个工作包括若干道工序，每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。 现在给出这些参数，求最大利润

题解：

网络流最大权闭合子图模型。

最大权闭合子图模型的答案通解为所有收益-最小割。

这道题因为加入了租用，与普通建图略有区别。

考虑存在的三条流：

1. S->项目
2. 项目->机器
3. 机器->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;
}