如果用单个点代表每个区间 利用拆点来限制区间的流量的话 点是 n^2/2+m个 边是2*n^2条

但是这样会T

解法1:单纯形

单纯形套板可以过

#include 
      
       #define Nusing namespace std;typedef unsigned ui;typedef long double dbl;const dbl eps = 1e-8;ui n, m, c[5001]; dbl a[4001][201], x[201], z;int dcmp(dbl d) { return d < -eps ? -1 : d <= eps ? 0 : 1; }//    u in, v outvoid pivot(ui u, ui v) {    swap(c[n + u], c[v]);    //    row u *= 1 / a[u][v]    dbl k = a[u][v]; a[u][v] = 1;    for (ui j = 0; j <= n; ++j) a[u][j] /= k;    for (ui i = 0; i <= m; ++i) {        if (i == u || !dcmp(a[i][v])) continue;        k = a[i][v]; a[i][v] = 0;        for (ui j = 0; j <= n; ++j)            a[i][j] -= a[u][j] * k;    }}bool init() {    for (ui i = 1; i <= n; ++i) c[i] = i;    while (1) {        ui u = 0, v = 0;        for (ui i = 1; i <= m; ++i)            if (dcmp(a[i][0]) == -1 && (!u || dcmp(a[u][0] - a[i][0]) == 1)) u = i;        if (!u) return 1;        for (ui j = 1; j <= n && !v; ++j)            if (dcmp(a[u][j]) == -1) v = j;        if (!v) return 0;        pivot(u, v);    }}int simplex() {    if (!init()) return 0;    else while (1) {        ui u = 0, v = 0;        for (ui j = 1; j <= n; ++j)            if (dcmp(a[0][j]) == 1 && (!v || a[0][j] > a[0][v])) v = j;        if (!v) {            z = -a[0][0];            for (ui i = 1; i <= m; ++i)                x[c[n + i]] = a[i][0];            return 1;        }        dbl w = 1e20;        for (ui i = 1; i <= m; ++i)            if (dcmp(a[i][v]) == 1 &&                dcmp(w - a[i][0] / a[i][v]) == 1) {                w = a[i][0] / a[i][v];                u = i;            }        if (!u) return 2;        pivot(u, v);    }}int main(void) {    ios::sync_with_stdio(0); cin.tie(0);#ifndef ONLINE_JUDGE    ifstream cin("1.in");#endif    ui t;    cin >> n >> m;    for (ui j = 1; j <= n; ++j) cin >> a[0][j];    for (ui i = 1; i <= m; ++i) {        int l, r; cin >> l >> r;        for (int j = l; j <= r; ++j)            a[i][j] = 1;        cin >> a[i][0];    }    int res = simplex();    if (res == 0) cout << "Infeasible" << endl;    else if (res == 2) cout << "Unbounded" << endl;    else {        cout << (long long)z << endl;    }    return 0;}
      

解法2:网络流

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #define inf 0x3f3f3f3ftypedef long long ll;using namespace std;const int maxn=300;const int maxm=10005;struct node{ int t,f,c,next;}e[maxm*2];int a[maxn];int head[maxn],dis[maxn],vis[maxn];int pre[maxn];int cnt,s,t;void add(int s,int t,int c,int f){ e[cnt].t=t; e[cnt].c=c; e[cnt].f=f; e[cnt].next=head[s]; head[s]=cnt++; e[cnt].t=s; e[cnt].c=0; e[cnt].f=-f; e[cnt].next=head[t]; head[t]=cnt++;}void intt(){ cnt=0; s=0;t=250; memset(head,-1,sizeof(head));}int spfa(){ queue
                
                 que; for(int i=0;i
                 
                  0&&dis[u]+e[i].f
                  
                   =2;i--) add(i,i-1,inf,0); for(int i=n+1;i>=1;i--) { int temp=a[i]-a[i-1]; if(temp<0) { add(i,t,-temp,0); } else add(s,i,temp,0); } printf("%lld\n",mincost());}
                  
                 
                
               
              
             
            
           
          
         
        
       
      

转载自 不懂原理QAQ