%%%hzw

表示没学过线性规划就来学这玩意QAQ。。听说拿来骗分很好用。。时间复杂度玄学？[O_{（跑得过）}

BZOJ-1061 单纯形板子题

[Noi2008]志愿者招募

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

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

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

//单纯形板子题 
#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;
}