BZOJ 1391 [Ceoi2008]order

题目大意

给你一些工作，每个工作都需要使用一些特定型号的机器，完成可以获得报酬。机器可以选择租赁或者购买，购买仅需一次，租赁需要个工作租赁一次。求最大的总收益。

这题数据范围也不大……一看就是网络流。S向工作连边，权值为工作收益，工作向机器连边，权值为租赁费用，机器向T连边，权值为购买费用，跑一遍最小割就可以了。

注意这题会超时，需要用一种优化——当前弧优化。记录一下Dinic的时候访问的最后一条边，在之后再次抵达之后从最后一条访问的边边开始搜索就可以了，因为之前的边如果再次搜索也只会返回0。注意这是只每次dinic()的时候进行的操作，和BFS()无关，在BFS()的时候要初始化当前弧cur[i]数组为head[i]。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 1<<30
#define N 2500
#define M 5000010
int n,m,ix,iy,iz,S,T,depth[N],ans,cur[N];
int to[M],nex[M],val[M],head[N],tot=1;
queue<int>q;
inline void AE(int tx,int ty,int tz)
{
	to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz;
	to[++tot]=tx,nex[tot]=head[ty],head[ty]=tot,val[tot]=0;
}
bool bfs()
{
	for(int i=S;i<=T;++i) cur[i]=head[i];
	while(!q.empty()) q.pop();
	q.push(S);
	memset(depth,-1,sizeof depth);
	depth[S]=0;
	while(!q.empty())
	{
		int tmp=q.front();
		q.pop();
		for(int i=head[tmp];i;i=nex[i]) if(val[i]&&depth[to[i]]==-1)
		{
			depth[to[i]]=depth[tmp]+1;
			if(to[i]==T) return true;
			q.push(to[i]);
		}
	}
	return false;
}
int dinic(int pos,int left)
{
	if(pos==T) return left;
	int nleft=left;
	for(int i=cur[pos];i;cur[pos]=i,i=nex[i]) if(val[i]&&depth[to[i]]==depth[pos]+1)
	{
		int tmp=dinic(to[i],min(val[i],nleft));
		if(!tmp) depth[to[i]]=0;
		nleft-=tmp;
		val[i]-=tmp;
		val[i^1]+=tmp;
		if(!nleft) break;
	}
	return left-nleft;
}
int main()
{
	scanf("%d%d",&n,&m);
	T=n+m+1;
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d",&ix,&iz),AE(S,i,ix),ans+=ix;
		for(int j=1;j<=iz;++j) scanf("%d%d",&ix,&iy),AE(i,ix+n,iy);
	}
	for(int i=1;i<=m;++i) scanf("%d",&ix),AE(i+n,T,ix);
	while(bfs()) ans-=dinic(S,INF);
	printf("%d\n",ans);
	return 0;
}