当前位置：首页 > news >正文

BZOJ1061 NOI2008 志愿者招募

news 来源：原创 2024/5/7 10:11:34

传送门

本来是费用流神建模但是被单纯形搞定了鸭2333

$\\m_{1,1}x_1 +m_{1,2}x_2 +...+m_{1,m}x_m\geq A_1 \\... \\m_{n,1}x_1 +m_{n,2}x_2 +...+m_{n,m}x_m\geq A_n$

$\forall i \epsilon [1,m]\ x_i\geq 0$

mi,j表示第i天第j种志愿者能否工作 Ai表示第i天至少要用的人数

$minimize\ \sum_{i=1}^n C_ix_i$

要最小化代价（目标函数）不是标准型所以根据线性规划的对偶性就可以做了qwqqq

线性规划的对偶性：

如果

$\\maximize\ c^T x \\subject\ to\ Ax \preceq b \\x\succeq0$ 和 $\\minimize\ b^T x \\subject\ to\ A^Tx \preceq c \\x\succeq 0$

均有可行解，则他们最优解相同或同时为Unbounded

这个题需要满足最优解是整数~~（你又不可能把人劈开）~~

但是实际上这个矩阵的性质就保证了最优解是整数（证明可戳洛咕题解）

扔代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define inf 2002122500
#define ll long long
#define db double
#define mxn 1010
#define mxm 10100
#define eps 1e-8
using namespace std;

db M[mxm][mxn];int n,m;
void privot(int x,int y)
{
	db tmp=1.0/M[x][y];
	M[x][y]=1.0;
	for(int i=0;i<=m;i++)	M[x][i]*=tmp;
	for(int i=0;i<=n;i++)
	{
		if(i==x||abs(M[i][y])<eps)	continue;
		db t=M[i][y];M[i][y]=0.0;
		for(int j=0;j<=m;j++)
			M[i][j]-=t*M[x][j];
	} 
}

bool simplex()
{
	while(1)
	{
		int x=0,y=0;db mn=1e15;
		for(int i=1;i<=m;i++)	if(M[0][i]>eps){y=i;break;}
		//printf("%d %lf\n",y,M[0][y]);
		if(!y)	return true;
		for(int i=1;i<=n;i++)
		{
			if(M[i][y]>eps && M[i][0]/M[i][y] <mn)
			{
				mn=M[i][0]/M[i][y];
				x=i;
			}
		}
		//printf("%lf %d\n",mn,x);
		if(!x){printf("Unbounded\n");return false;}
		privot(x,y);
	}
	return true;
}

int main()
{
	int l,r;
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)	scanf("%lf",&M[0][i]);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%lf",&l,&r,&M[i][0]);
		for(int j=l;j<=r;j++)	M[i][j]=1.0;
	}
	if(simplex())	printf("%.0lf\n",-M[0][0]);
	return 0;
}

转载于:https://www.cnblogs.com/hanyuweining/p/10321940.html