正题

题目链接:https://www.luogu.com.cn/problem/P3337

题目大意

\(n\)个地方可以建立塔也可以不建立塔，第\(i\)个位置建立需要消耗\(C_i\)元

\(m\)个限制要求在某个区间内的塔的数量超过\(D_i\)

\(1\leq n\leq 1000,1\leq m\leq 10000\)

题目大意

抽象成数学模型的话

\[minimize\ \ \sum_{i=1}^nC_ix_i
\]

\[\sum_{l_i}^{r_i}x_{i,j}\geq D_i
\]

然后网络流好像草不过去，考虑点线性规划玄学算法

先把它对偶了

\[maximize\ \ \sum_{i=1}^nD_ix_i
\]

\[\sum_{l_i}^{r_i}x_{i,j}\leq C_i
\]

然后就是一个裸的单纯形了。

所以单纯形是什么，这里就粗略的讲一下。

我是看线性规划与单纯形算法-吴一凡的课件学的

对于普通的松弛型有三个限制：

对于每个\(i\)满足\(\sum_{j=1}^nA_{i,j}x_j+x_{n+i}=b_i\)
\(x_{n+i}\geq 0\)
最大化\(\sum_{i=1}^nx_ic_i\)

定义所有的\(x_{n+i}\)为基变量，\(x_i(i\leq n)\)为非基变量

然后单纯形的流程就是先找出任意一个\(c_i\)为正的基变量\(x_p\)

然后去掉所有其他非基变量后得到一个对于\(x_p\)最小的限制，即最小的\(\frac{c_p}{a_{p,z}}\)

然后考虑交换非基变量\(x_p\)和基变量\(x_{z+n}\)，此时可以得到一个由第\(z\)行的式子推出的关于\(x_p\)的式子，带入回到需要最大化的式子当中。此时由于\(c_i\)为正，所以式子中会有一个正的常数。

此时这个常数就相当于大化了那个式子，不停重复上面的转轴操作直到无法找到正的\(c_i\)为止（此时就代表无法继续扩大了）

这个是实数的，但是我们这题的要求是整数，但是我们这里的约束矩阵\(A\)是一个全幺模矩阵，所以至少保证有一组最优解全是整数，又不用输出方案，直接单纯形暴艹就可以了

复杂度比较玄学，但是能过这题

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=1100;

const double eps=1e-8,inf=1e9;

int n,m;double c[N],w[N*10],a[N][N*10],ans;

void Pivot(int l,int e){

	c[l]/=a[l][e];

	for(int i=1;i<=m;i++)

		if(i!=e)a[l][i]/=a[l][e];

	a[l][e]=1.0;

	for(int i=1;i<=n;i++)

		if(i!=l&&fabs(a[i][e])>eps){

			c[i]-=a[i][e]*c[l];

			for(int j=1;j<=m;j++)

				if(j!=e)a[i][j]-=a[i][e]*a[l][j];

			a[i][e]=-a[i][e]*a[l][e];

		}

	ans+=w[e]*c[l];

	for(int i=1;i<=m;i++)

		if(i!=e)w[i]-=w[e]*a[l][i];

	w[e]=-w[e]*a[l][e];

}

double simplex(){

	while(1){

		double mins=inf;

		int i=0,j=0,k=0;

		for(j=1;j<=m;j++)

			if(w[j]>eps)break;

		if(j>m)return ans;

		for(i=1;i<=n;i++)

			if(a[i][j]>eps&&mins>c[i]/a[i][j])

				k=i,mins=c[i]/a[i][j];

		if(mins>=inf)return inf;

		Pivot(k,j);

	}

}

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 l,r;

		scanf("%d%d%lf",&l,&r,&w[i]);

		for(int j=l;j<=r;j++)a[j][i]=1.0;

	}

	printf("%d\n",(int)(simplex()+0.5));

	return 0;

}

巴特西

P3337-[ZJOI2013]防守战线【单纯形】

正题

题目大意

题目大意

code

最新文章

热门文章