BZOJ1061 NOI2008 志愿者招募-白红宇

BZOJ1061 NOI2008 志愿者招募

阅读量：6509 次

发布时间：2019-06-24

本文共 821 字，大约阅读时间需要 2 分钟。

本来是费用流神建模但是被单纯形搞定了鸭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
    
     #include
     
      #include
      
       #include
       
        #define inf 2002122500#define ll long long#define db double#define mxn 1010#define mxm 10100#define eps 1e-8using 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){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]