Pluto_Rabbit's Blog

蒟蒻妹纸一枚,轻拍

【学习】单纯形法

Jacinth posted @ 2016年3月20日 15:12 in ZHOJ with tags BZOJ Learning 单纯形法 费用流 学习 , 186 阅读

%%%hzw

表示没学过线性规划就来学这玩意QAQ。。听说拿来骗分很好用。。时间复杂度玄学?[O(跑得过)

BZOJ-1061 单纯形板子题

[Noi2008]志愿者招募

Description

申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难题:为即将启动的奥运新项目招募一批短期志愿者。经过估算,这个项目需要N 天才能完成,其中第i 天至少需要Ai 个人。

布布通过了解得知,一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天,招募费用是每人Ci 元。新官上任三把火,为了出色地完成自己的工作,布布希望用尽量少的费用招募足够的志愿者,但这并不是他的特长!于是布布找到了你,希望你帮他设计一种最优的招募方案。

Input 第一行包含两个整数N, M,表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负整数,表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci,含义如上文所述。为了方便起见,我们可以认为每类志愿者的数量都是无限多的。
Output
仅包含一个整数,表示你所设计的最优方案的总费用。
Sample Input
3 3
2 3 4
1 2 2
2 3 5
3 3 2
Sample Output 14
Hint 招募第一类志愿者3名,第三类志愿者4名 30%的数据中,1 ≤ N, M ≤ 10,1 ≤ Ai ≤ 10; 100%的数据中,1 ≤ N ≤ 1000,1 ≤ M ≤ 10000,题目中其他所涉及的数据均 不超过2^31-1。

听说是单纯形裸题。。费用流建图好题。。

两个方法都试了一遍。。。(谁说单纯形跑得慢?难道窝费用流写炸?

Problem Result Memory Time Code_Length
1061 Accepted 80344 kb 1172 ms 1376 B
1061 Accepted 3264 kb 1424 ms 1804 B

还是把两个代码都贴在这里吧

//单纯形板子题 
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 1e10
#define eps 1e-7
#define NN 1010
#define MM 10010
using namespace std;
int n,m;
double a[MM][NN],b[MM],c[NN],v,ans;
struct S
{
	void Pivot(int l,int e)
	{
		int i,j;
		b[l]/=a[l][e];
		for (i=1;i<=n;++i) if (i!=e) a[l][i]/=a[l][e];
		a[l][e]=1/a[l][e];
		for (i=1;i<=m;++i)
		if (i!=l && fabs(a[i][e])>eps)
		{
			b[i]-=a[i][e]*b[l];
			for (j=1;j<=n;++j)
				if (j!=e) a[i][j]-=a[i][e]*a[l][j];
			a[i][e]=-a[i][e]*a[l][e];
		}
		v+=c[e]*b[l];
		for (i=1;i<=n;++i)
			if (i!=e) c[i]-=c[e]*a[l][i];
		c[e]=-c[e]*a[l][e];
	}
	double simplex()
	{
		int i,l,e;
		while (1)
		{
			for (i=1;i<=n;++i) if (c[i]>eps) break;
			if ((e=i)==n+1) return v;
			double tmp=INF;
			for (i=1;i<=m;++i)
				if (a[i][e]>eps && b[i]/a[i][e]<tmp) tmp=b[i]/a[i][e], l=i;
			if (tmp==INF) return INF;
			Pivot(l,e);
		}
	}
}Simplex;
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf("%lf",&c[i]);
	for (int i=1;i<=m;++i)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		for (int j=x;j<=y;++j) a[i][j]=1; b[i]=z;
	}
	ans=Simplex.simplex();
	printf("%d\n",int(ans+0.5));
	return 0;
}
//费用流 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define LL long long
#define NN 2010
#define MM 100010
#define INF 0x3f3f3f3f
using namespace std;
int n,m,x,y,z,dis[NN],head[NN],fa[NN],need[NN],S,T,tot=1;
bool vis[NN];
LL ans=0;
struct REC
{
	int v,ne,w,c,u;
}e[MM];
queue<int>que;
void Build(int xx,int yy,int zz,int cc)
{
	e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz, e[tot].c=cc, e[tot].u=xx;
	e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx, e[tot].w=0, e[tot].c=-cc, e[tot].u=yy;
}
bool SPFA()
{
	while (!que.empty()) que.pop();
	memset(dis,INF,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[S]=0, que.push(S), vis[S]=1;
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=e[i].ne)
		if (e[i].w && dis[e[i].v]>dis[now]+e[i].c)
		{
			dis[e[i].v]=dis[now]+e[i].c; fa[e[i].v]=i;
			if (!vis[e[i].v]) vis[e[i].v]=1, que.push(e[i].v);
		}
		vis[now]=0;
	}
	return dis[T]!=INF;
}

void MCF()
{
	int xx=INF;
	for (int i=fa[T];i;i=fa[e[i].u]) xx=min(xx,e[i].w);
	for (int i=fa[T];i;i=fa[e[i].u]) ans+=(LL)xx*e[i].c, e[i].w-=xx, e[i^1].w+=xx;
}

int main()
{
	scanf("%d%d",&n,&m); S=n+2, T=n+3;
	for (int i=1;i<=n;++i) scanf("%d",&need[i]);
	for (int i=1;i<=m;++i)
		scanf("%d%d%d",&x,&y,&z), Build(x,y+1,INF,z);
	need[0]=need[n+1]=0;
	int tmp;
	for (int i=1;i<=n+1;++i) if ((tmp=need[i]-need[i-1])>=0) Build(S,i,tmp,0); else Build(i,T,-tmp,0);
	for (int i=1;i<=n;++i) Build(i+1,i,INF,0);
	while (SPFA()) MCF();
	printf("%lld\n",ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter