两题基本一个货色, 都是单纯形法的板子
不过在暴力上单纯形法之前还有一个问题, 题目中我们可以推出的线性规划式子是这样的:
\[ \text{LP}\\\min f(x)=c^T x\\s.t. Ax\ge b\\x\ge 0 \]
好像不是单纯形法的形式啊? 然而我们根据经典的对称型线性规划对偶得知 (不知道的可以看下这个, 里面的例子很好理解)
\[ \text{Dual LP}\\\max g(y)=b^Ty\\s.t. A^Ty\le c\\y\ge 0 \]
就可以直接上了, 然后由于这题里的系数都是 \(-1,0,1\), 又被称为全幺模矩阵, 有关它的更多姿势这里不再介绍因为我也不会, 结合单纯形法的线代姿势得知最后的答案也一定是整数 (因为相当于在做行变换), 就没有问题了
- BZOJ 1061
- #include<cstdio>
- #include<cmath>
- #include<iostream>
- #include<cstdlib>
- #define RI register int
- #define CI const int&
- using namespace std;
- const int N=1005,M=10005;
- const double EPS=1e-8;
- int n,m,tp,l,r; double a[M][N];
- namespace SM //Simplex Method
- {
- int id[N+M];
- inline void pivot(CI l,CI e)
- {
- RI i,j; swap(id[n+l],id[e]); double t=a[l][e];
- for (a[l][e]=1,i=0;i<=n;++i) a[l][i]/=t;
- for (i=0;i<=m;++i) if (i!=l&&fabs(a[i][e])>EPS)
- for (t=a[i][e],a[i][e]=j=0;j<=n;++j) a[i][j]-=t*a[l][j];
- }
- inline void simplex(void)
- {
- for (;;)
- {
- RI i; int l=0,e=0; double mi=1e9;
- for (i=1;i<=n;++i) if (a[0][i]>EPS) { e=i; break; } if (!e) break;
- for (i=1;i<=m;++i) if (a[i][e]>EPS&&a[i][0]/a[i][e]<mi) mi=a[i][0]/a[i][e],l=i; pivot(l,e);
- }
- }
- };
- int main()
- {
- RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%lf",&a[0][i]);
- for (i=1;i<=m;++i) for (scanf("%d%d%lf",&l,&r,&a[i][0]),j=l;j<=r;++j) a[i][j]=1;
- return SM::simplex(),printf("%d",(int)(-a[0][0]+0.5)),0;
- }
- BZOJ 3265
- #include<cstdio>
- #include<cmath>
- #include<iostream>
- #include<cstdlib>
- #define RI register int
- #define CI const int&
- using namespace std;
- const int N=1005,M=10005;
- const double EPS=1e-8;
- int n,m,s,tp,l,r; double a[M][N];
- namespace SM //Simplex Method
- {
- int id[N+M];
- inline void pivot(CI l,CI e)
- {
- RI i,j; swap(id[n+l],id[e]); double t=a[l][e];
- for (a[l][e]=1,i=0;i<=n;++i) a[l][i]/=t;
- for (i=0;i<=m;++i) if (i!=l&&fabs(a[i][e])>EPS)
- for (t=a[i][e],a[i][e]=j=0;j<=n;++j) a[i][j]-=t*a[l][j];
- }
- inline void simplex(void)
- {
- for (;;)
- {
- RI i; int l=0,e=0; double mi=1e9;
- for (i=1;i<=n;++i) if (a[0][i]>EPS) { e=i; break; } if (!e) break;
- for (i=1;i<=m;++i) if (a[i][e]>EPS&&a[i][0]/a[i][e]<mi) mi=a[i][0]/a[i][e],l=i; pivot(l,e);
- }
- }
- };
- int main()
- {
- RI i,j,k; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%lf",&a[0][i]);
- for (i=1;i<=m;++i)
- {
- for (scanf("%d",&s),k=1;k<=s;++k)
- for (scanf("%d%d",&l,&r),j=l;j<=r;++j) a[i][j]=1;
- scanf("%lf",&a[i][0]);
- }
- return SM::simplex(),printf("%d",(int)(-a[0][0]+0.5)),0;
- }
来源: http://www.bubuko.com/infodetail-3408442.html