[文章目录]
Description
有N个工作，M种机器，每种机器你可以租或者买过来. 每个工作包括若干道工序，每道工序需要某种机器来完成,你可以通过购买或租用机器来完成。 现在给出这些参数，求最大利润(1<=N<=1200,1<=M<=1200)
网络流最小割（纳尼？我居然把板子敲错了，不可饶恕）
源点向每个工作连边，流量为收益，工作向租用机器连边，流量为租金，机器向汇点连边，流量为购买价格。总收益减去最小割就是答案。
然而，亲测TLE。。。然后网上说要加一个什么当前弧优化（在dinic算法中）。也挺简单的，就是每次在寻找增广路径的时候，到达一个点，直接从其没有搜过的边开始搜索，对于搜过的边，由于已经满流，所以没有必要扫。
对于每个点记录一个数组cur[x]，表示x点第一个没有被搜过的出边，在搜索的时候直接更新cur的值。注意，每次bfs之后需初始化cur数组（cur[i]=head[i]）。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,s,t,ans;
int head[2500],cur[2500],nxt[3300000],to[3300000],f[3300000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
queue<int>q;
int dis[2500];
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
dis[s]=0; int x; q.push(s);
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int &i=cur[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) return flow;
}
return flow-tmp;
}
int main()
{
scanf("%d%d",&n,&m); s=n+m+1; t=s+1;
int x,y,z;
for(int i=1;i<=n;++i)
{
scanf("%d%d",&x,&z);
ans+=x; add(s,i,x);
while(z--)
{
scanf("%d%d",&x,&y);
add(i,n+x,y);
}
}
for(int i=1;i<=m;++i)
{
scanf("%d",&x);
add(n+i,t,x);
}
while(bfs())
{
for(int i=1;i<=t;++i) cur[i]=head[i];
ans-=dinic(s,inf);
}
printf("%d",ans);
return 0;
}