orz
题解戳这里
暂时只能理解下
由于不等式不能作差，加上Yi变成等式作差
作差后每个X最多出现一次，这样就可以考虑两个之间的影响了（通过连边，这里流出去这么多那里就要流进来这么对，对应一正一负）
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 void setIO(const string& s) { 10 freopen((s + ".in").c_str(), "r", stdin); 11 freopen((s + ".out").c_str(), "w", stdout); 12 } 13 template Q read(Q& x) { 14 static char c, f; 15 for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1; 16 for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0'; 17 if(f) x = -x; 18 return x; 19 } 20 template Q read() { 21 static Q x; read(x); return x; 22 } 23 // MCMF 24 25 const int N = 1000 + 10, M = 25000 + 10, INF = ~0u >> 1; 26 27 struct Edge { 28 int to, adv, cost; 29 Edge *next; 30 Edge(int to = 0, int adv = 0, int cost = 0, Edge *next = 0) : to(to), adv(adv), cost(cost), next(next) {} 31 }pool[M * 2], *pis = pool, *fir[N]; 32 33 void AddEdge(int u, int v, int w, int c) { 34 fir[u] = new(pis++) Edge(v, w, c, fir[u]); 35 fir[v] = new(pis++) Edge(u, 0, -c, fir[v]); 36 } 37 38 #define inv(p) (pool + ( ((p) - pool)^1 )) 39 40 namespace MCMF { 41 int n, s, t; 42 int d[N], q[N], ql, qr, a[N]; 43 Edge *pre[N]; 44 bool inq[N]; 45 46 bool insert(int u, int dis, int aug) { 47 if(d[u] > dis) { 48 a[u] = aug; 49 d[u] = dis; 50 if(!inq[u]) { 51 q[qr++] = u; 52 if(qr == N) qr = 0; 53 inq[u] = 1; 54 } 55 return 1; 56 }return 0; 57 } 58 59 bool SPFA(int& flow, int& cost) { 60 for(int u = 1; u <= n; u++) d[u] = INF, inq[u] = 0; 61 insert(s, 0, INF); 62 while(ql ^ qr) { 63 int u = q[ql++]; if(ql == N) ql = 0; inq[u] = 0; 64 for(Edge *p = fir[u]; p; p = p->next) if(p->adv) { 65 if(insert(p->to, d[u] + p->cost, min(a[u], p->adv))) { 66 pre[p->to] = p; 67 } 68 } 69 } 70 if(d[t] == INF) return 0; 71 flow += a[t]; 72 cost += d[t] * a[t]; 73 for(int u = t; u != s; u = inv(pre[u])->to) { 74 pre[u]->adv -= a[t]; 75 inv(pre[u])->adv += a[t]; 76 } 77 return 1; 78 } 79 80 int main(int _n ,int _s, int _t) { 81 n = _n, s = _s, t = _t; 82 int flow = 0, cost = 0; 83 while(SPFA(flow, cost)); 84 return cost; 85 } 86 } 87 88 const int maxn = 1000 + 10, maxm = 10000 + 10; 89 int demand[maxn]; 90 91 int main() { 92 #ifdef DEBUG 93 freopen("in.txt", "r", stdin); 94 freopen("out.txt", "w", stdout); 95 #endif 96 97 int n = read (), m = read (); 98 int s = n + 2, t = s + 1; 99 for(int i = 1; i <= n; i++) {100 read(demand[i]);101 AddEdge(i + 1, i, INF, 0);102 }103 for(int i = 1; i <= n + 1; i++) {104 int dlt = demand[i] - demand[i - 1];105 if(dlt >= 0) AddEdge(s, i, dlt, 0);106 else AddEdge(i, t, -dlt, 0);107 }108 int l, r, c;109 for(int i = 1; i <= m; i++) {110 read(l), read(r), read(c);111 AddEdge(l, r + 1, INF, c);112 }113 114 printf("%d\n", MCMF::main(t, s, t));115 116 return 0;117 }
vijos1891类似