整数线性规划与全幺模矩阵

全幺模矩阵（totally unimodular matrix）是指任何一个行数和列数相等的满秩子矩阵行列式的值都是1或-1的矩阵。

其意义在于，若$\mathbf {A}$为全幺模矩阵， 对线性规划
$$ \mathbf{Ax}\le \mathbf{b,x\ge 0}\\\\ \text{Maximize }\sum c_ix_i $$
执行单纯性法过程中涉及的所有约束的系数$\in\{-1,0,1\}$. 那么$x_i$限制为实数和限制为$\{0,1\}$ 时答案相同。即这样的整数线性规划（整数线性规划本身为NP问题，单纯形法亦无法求解）的答案与实数线性规划的答案相同。同样套用单纯形法即可（均为整数还可以优化常数）

考虑此题怎么变成线性规划。

由题意得：
$$ \sum_{L_j\le i\le R_j}x_j\ge a_i(i\in[1,n])\\\\ x_i\ge 0\\\\ \text{Minimize} \sum_ic_ix_i $$

对偶之后得：
$$ \sum_{L_i\le j\le R_i}x_j\le c_i(i\in [1,m])\\\\ x_i\ge 0\\\\ \text{Maximize} \sum a_ix_i $$

单纯性直接上就好了，能过的。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<set>
typedef long long ll;
typedef unsigned un;
typedef std::vector<int> P;
typedef std::pair<int,int> pii;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
template <typename T> bool umax(T& a,T t){if(t>a)return a=t,1;return 0;}
template <typename T> bool umin(T& a,T t){if(t<a)return a=t,1;return 0;}
double fabs(double x){return x>0?x:-x;}
bool is_zero(double x){return x<1e-7&&-x<1e-7;}
/**********/
const int MAXN = 1011,MAXM = 10011;
//LP on {-1,0,1}
int a[MAXM][MAXN],n,m;
int dex[MAXM<<1|1];
void pivot(int B,int N)
{
    if(!a[B][N]){std::cerr<<"ERR!";exit(-5);}
    int rate=a[B][N];
    //printf("Rate=%d\n",rate);
    a[B][N]=1;
    for(int j=0;j<=n;++j)a[B][j]*=rate;
    for(int i=0;i<=m;++i)
        if(i!=B)
        {
            int rate=a[i][N];
            if(!rate)continue;
            a[i][N]=0;
            for(int j=0;j<=n;++j)a[i][j]-=a[B][j]*rate;
        }
    //std::swap(dex[m+B],dex[N]);
}
void prt()
{
    puts("Prt:");
    for(int i=0;i<=m;++i,puts(""))
        for(int j=0;j<=n;++j)printf("%d ",a[i][j]);
}
int simplex()
{
    //prt();
    while(1)
    {
        int B=-1,N=-1;
        for(int i=1;i<=n;++i)
            if(a[0][i]>0){N=i;break;}
        if(N<0)break;
        int minv=1e9;
        for(int i=1;i<=m;++i)
            if(a[i][N]==1&&umin(minv,a[i][0]))B=i;
        if(B<0){return 1e9+233;}
        pivot(B,N);
        //prt();
    }
    return -a[0][0];
}
int need[MAXN];
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i)need[i]=read(),a[0][i]=need[i];
    for(int i=1;i<=m;++i)
    {
        int l=read(),r=read(),c=read();
        for(int j=l;j<=r;++j)a[i][j]=1;
        a[i][0]=c;
    }
    printf("%d\n",simplex());
    return 0;
}