正題

題目鏈接:https://www.luogu.com.cn/problem/P3337

---

題目大意

$n$個地方可以建立塔也可以不建立塔，第$i$個位置建立需要消耗$C_i$元

$m$個限制要求在某個區間內的塔的數量超過$D_i$

$1\le n\le 1000,1\le m\le 10000$

---

題目大意

抽象成數學模型的話
$$minimize\sum _{i=1}^n{C}_i{x}_i$$
$$\sum _{l_i}^{r_i}{x}_{i,j}\ge D_i$$
然后網絡流好像草不過去，考慮點線性規劃玄學算法

先把它對偶了
$$maximize\sum _{i=1}^n{D}_i{x}_i$$
$$\sum _{l_i}^{r_i}{x}_{i,j}\le C_i$$

然后就是一個裸的單純形了。

所以單純形是什么，這里就粗略的講一下。
我是看線性規劃與單純形算法-吳一凡的課件學的

對于普通的松弛型有三個限制：

對于每個$i$滿足${\sum }_{j=1}^n{A}_{i,j}{x}_j+x_{n+i}=b_i$

$x_{n+i}\ge 0$

最大化${\sum }_{i=1}^n{x}_i{c}_i$

定義所有的$x_{n+i}$為基變量，$x_i(i\le 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]防守战线【单纯形】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。