【BZOJ1221】【HNOI2001】软件开发

  这题和线性规划与网络流24题里的餐巾计划问题基本一样，除了这里的餐巾洗了x天后第x+1天才能投入使用。

  一直对这类建模理解的不是很透彻。（还有题目叫软件开发什么鬼）

  将第i天用完的毛巾和需要用的毛巾分成Xi,Yi两个点集处理。

  每天用完的毛巾有Ni条，从S向Xi连一条流量为Ni，费用为0的边来约束；

  每天需要用Ni条毛巾，从Yi向T连一条流量为Ni，费用为0的边来约束；

  每天用完的毛巾一部分送去快洗，从Xi向Yi+n+a+1连一条流量为inf，费用为fA的边；

  还有送去慢洗的，从Xi向Yi+n+b+1连一条流量为inf，费用为fB的边；

  还有留着先不处理留到第二天的，从Xi向Xi+1连一条流量为inf，费用为fB的边；

  每天可能需要新买毛巾，从S向Yi连一条流量为inf，费用为f的边。

  建图建完做一遍最小费用最大流就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=2010,maxe=maxn*6,inf=~0U>>1;

int head[maxn],next[maxe],E[maxe],F[maxe],C[maxe],Ecnt;
int n,a,b,f,fA,fB;
int S,T;

void Add_Edge(int x,int y,int flow,int cost)
{
	next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;F[Ecnt]=0;C[Ecnt]=cost;
	next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;F[Ecnt]=flow;C[Ecnt]=-cost;
}

int vis[maxn];
int q[maxn],qhead,qtail;
int dis[maxn];

int inc(int x) {return (x+1)%maxn;}
int dec(int x) {return (x-1+maxn)%maxn;}

bool Spfa(int st,int ed)
{
	memset(vis,0,sizeof(vis));
	memset(dis,0x7F,sizeof(dis));
	q[qhead=qtail=0]=st;
	vis[st]=1;dis[st]=0;
	while (qhead!=inc(qtail))
	{
		int x=q[qhead];
		qhead=inc(qhead);
		vis[x]=0;
		for (int i=head[x];i;i=next[i]) if (F[i] && dis[E[i]]>dis[x]-C[i])
		{
			dis[E[i]]=dis[x]-C[i];
			if (!vis[E[i]])
				if (qhead!=inc(qtail) && dis[q[qhead]]>dis[E[i]]) q[qhead=dec(qhead)]=E[i];else q[qtail=inc(qtail)]=E[i];
			vis[E[i]]=1;
		}
	}
	return dis[ed]!=0x7F7F7F7F;
}

int DFS(int x,int flow,int &res)
{
	vis[x]=1;
	if (x==T) return flow;
	int rest=flow;
	for (int i=head[x];i && rest;i=next[i])
		if (dis[E[i]]==dis[x]-C[i] && F[i^1] && !vis[E[i]])
		{
			int d=DFS(E[i],min(rest,F[i^1]),res);
			res+=d*C[i];
			rest-=d;F[i]+=d;F[i^1]-=d;
		}
	return flow-rest;
}

void Min_Cost_Flow()
{
	int res=0;
	while (Spfa(T,S))
	{
		vis[T]=1;
		while (vis[T])
		{
			memset(vis,0,sizeof(vis));
			DFS(S,inf,res);
		}
	}
	printf("%d\n",res);
}

int main()
{
	scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&fA,&fB);
	S=n*2+1;T=S+1;Ecnt=1;
	for (int i=1;i<=n;i++)
	{
		if (i+1<=n) Add_Edge(i,i+1,inf,0);
		if (i+a+1<=n) Add_Edge(i,i+a+n+1,inf,fA);
		if (i+b+1<=n) Add_Edge(i,i+b+n+1,inf,fB);
		Add_Edge(S,i+n,inf,f);
		int x;scanf("%d",&x);
		Add_Edge(S,i,x,0);
		Add_Edge(i+n,T,x,0);
	}
	Min_Cost_Flow();
	return 0;
}

  事实上这道题是可以用求单峰函数极值做的。

  具体做法来源见BZOJ1229，下面贴个代码。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1010,inf=~0U>>1;

int n,N1,N2,C1,C2,Tc;
int a[maxn],asum;
int ans;

int q[maxn],top1,top2;
int fa[maxn];

int Find(int x) {return (fa[x]==x)?x:fa[x]=Find(fa[x]);}

int f(int x)
{
	for (int i=1;i<=n;i++) q[i]=a[i],fa[i]=i;
	top1=1;top2=0;
	int res=Tc*x;
	for (int i=1;i<=n;i++)
	{
		top2=i-N1;
		if (x<a[i])
		{
			while (top1<=i-N2 && x<a[i])
			{
				int m=min(q[top1],a[i]-x);
				x+=m;
				q[top1]-=m;
				res+=C2*m;
				if (x<a[i]) top1++; 
			}
			while (top2>=top1 && x<a[i])
			{
				int m=min(q[top2],a[i]-x);
				x+=m;
				q[top2]-=m;
				res+=C1*m;
				if (x<a[i]) fa[top2]=Find(top2-1),top2=fa[top2];
			}
			if (x<a[i]) return inf;
		}
		x-=a[i];
	}
	return res;
}

int main()
{
	scanf("%d%d%d%d%d%d",&n,&N1,&N2,&Tc,&C1,&C2);
	N1++;N2++;
	if (N1>N2) swap(N1,N2),swap(C1,C2);
	if (C1<C2) C2=C1;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]),asum+=a[i];
	int l=0,r=asum;
	while (r-l>2)
	{
		int m1=l+(r-l)/3,m2=l+2*((r-l)/3);
		int fm1=f(m1),fm2=f(m2);
		if (fm1!=inf && fm1<=fm2) r=m2;else l=m1;
	}
	ans=inf;
	for (int i=l;i<=r;i++) ans=min(ans,f(i));
	printf("%d\n",ans);
	return 0;
}