題目描述

$n$ 個(gè)連續(xù)的位置，每個(gè)位置可以填入 S 和 E ，第 $i$ 個(gè)位置填入 S 可以獲得 $s_i$ 的收益，填入 E 可以獲得 $e_i$ 的收益。要求每連續(xù)的 $k$ 個(gè)位置必須包含至少 $t1$ 個(gè) S 和至少 $t2$ 個(gè) E ，問(wèn)最大收益以及方案。

輸入

第一行四個(gè)整數(shù),n,k(1<=k<=n<=1000),t1,t2(0<=t1,t2<=k;t1+t2<=k),含義如上所述。 接下來(lái)一行n個(gè)整數(shù)，第i個(gè)整數(shù)si(0<=si<=1e9)表示睡覺的愉悅值。 接下來(lái)一行n個(gè)整數(shù)，第i個(gè)整數(shù)ei(0<=ei<=1e9)表示打隔膜的愉悅值。

輸出

第一行輸出最大的愉悅值。 接下來(lái)一行輸出一個(gè)長(zhǎng)度為n的字符串 第i個(gè)字符為E則代表第i小時(shí)在打隔膜，第i個(gè)字符為S則代表第i個(gè)小時(shí)在睡覺。

樣例輸入

10 4 1 2
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

樣例輸出

69
EEESESEESS

---

題解

線性規(guī)劃與網(wǎng)絡(luò)流

首先設(shè) $x_i$ 表示第 $i$ 個(gè)位置是否填入 S ，是則為 1 ，否則為 0 。

那么先 “欽定” 所有的都為 $e_i$ ，把 $\sum\limits_{i=1}^ne_i$ 看作基本收益，然后再考慮 $x_i=1$ 的貢獻(xiàn)，相當(dāng)于 $x_i$ 為 1 時(shí)能夠獲得 $s_i-e_i$ 的收益。

因此我們要做的就是：最大化 $\sum\limits_{i=1}^n(s_i-e_i)$ ，滿足對(duì)于任意的 $p$ 均有 $t1\le\sum\limits_{i=p}^{p+k-1}x_i\le k-t2$ 。

此時(shí)由于 $x_i$ 僅為 1 或 0 的限制，不能使用單純形。

進(jìn)一步推導(dǎo)，添加輔助變量 $y_p$ 和 $z_p$ ，將限制條件轉(zhuǎn)變?yōu)榈仁疥P(guān)系：$t1+y_p=\sum\limits_{i=p}^{p+k-1}x_i= k-t2-z_p?$

于是我們就可以得到一大堆條件：

$\begin{cases}x_1+x_2+...+x_k=t1+y_1\\x_1+x_2+...+x_k=k-t2-z_1\\x_2+x_3+...+x_{k+1}=t1+y_2\\x_2+x_3+...+x_{k+1}=k-t2-z_2\\...\\...\\x_{n-k+1}+x_{n-k+2}+...+x_n=t1+y_{n-k+1}\\x_{n-k+1}+x_{n-k+2}+...+x_n=k-t2-z_{n-k+1}\end{cases}$

做題做的多了就很容易發(fā)現(xiàn)這些條件可以使用網(wǎng)絡(luò)流來(lái)求解線性規(guī)劃問(wèn)題，具體可以參考 [NOI2008]志愿者招募 題解?

繼續(xù)推導(dǎo)，在條件的前后加入恒等式 $0=0$ ，然后下面的與上面的作差，并移項(xiàng)，即可得到：

$\begin{cases}x_1+x_2+...+x_k=(t1)+y_1\\y_1+z_1=(k-t1-t2)\\x_{k+1}+(k-t1-t2)=x_1+z_1+y_2\\y_2+z_2=(k-t1-t2)\\...\\...\\y_{n-k+1}+z_{n-k+1}=(k-t1-t2)\\(k-t2)=x_{n-k+1}+x_{n-k+2}+...+x_n=z_{n-k+1}\end{cases}$

（用括號(hào)括起來(lái)的是常數(shù)項(xiàng)）

這個(gè)形式中每一個(gè)變量都出現(xiàn)且僅出現(xiàn)了兩次，且分別出現(xiàn)在等式左端與等式右端。

那么我們就可以使用網(wǎng)絡(luò)流來(lái)解決。

把等式看作點(diǎn)，左端看作流出，右端看作流入（每個(gè)點(diǎn)的流量平衡，對(duì)應(yīng)著等式的成立性）；每個(gè)變量從其在左邊的等式向其在右邊的等式連邊；對(duì)于常數(shù)項(xiàng)，出現(xiàn)在左邊則想?yún)R點(diǎn)連邊，否則源點(diǎn)向其連邊。

本題中變量 $x_i$ 的范圍為 $[0,1]$ ，因此連的邊容量為 1 ；又由于選 $x_i$ 會(huì)獲得 $s_i-e_i$ 的收益，因此要帶有費(fèi)用 $s_i-e_i$；

$y_i$ 和 $z_i$ 的范圍為 $[0,+\infty)$ ，因此連的邊容量為 inf ，費(fèi)用為0。

跑最大費(fèi)用最大流，最大費(fèi)用加上預(yù)先 “欽定” 好的 $\sum\limits_{i=1}^ne_i$ 即為最大收益。

輸出方案直接看哪些邊滿流即可。

時(shí)間復(fù)雜度 $O(費(fèi)用流)=O(能過(guò))$

#include <queue> #include <cstdio> #include <cstring> #define N 2010 #define M 20010 #define inf 1 << 30 using namespace std; typedef long long ll; queue<int> q; int head[N] , to[M] , val[M] , id[M] , next[M] , cnt = 1 , s , t , from[N] , pre[N] , opt[N]; ll a1[N] , a2[N] , cost[M] , dis[N]; inline void add(int x , int y , int v , ll c , int i) {to[++cnt] = y , val[cnt] = v , cost[cnt] = c , id[cnt] = i , next[cnt] = head[x] , head[x] = cnt;to[++cnt] = x , val[cnt] = 0 , cost[cnt] = -c , id[cnt] = 0 , next[cnt] = head[y] , head[y] = cnt; } bool spfa() {int x , i;memset(from , -1 , sizeof(from));memset(dis , 0xc0 , sizeof(dis));dis[s] = 0 , q.push(s);while(!q.empty()){x = q.front() , q.pop();for(i = head[x] ; i ; i = next[i])if(val[i] && dis[to[i]] < dis[x] + cost[i])dis[to[i]] = dis[x] + cost[i] , from[to[i]] = x , pre[to[i]] = i , q.push(to[i]);}return ~from[t]; } ll maxcost() {ll ans = 0;int i , k;while(spfa()){k = inf;for(i = t ; i != s ; i = from[i]) k = min(k , val[pre[i]]);ans += k * dis[t];for(i = t ; i != s ; i = from[i]) val[pre[i]] -= k , val[pre[i] ^ 1] += k;}return ans; } int main() {int n , k , t1 , t2 , i , l , r;ll ans = 0;scanf("%d%d%d%d" , &n , &k , &t1 , &t2) , s = 0 , t = 2 * n - 2 * k + 4;for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &a1[i]);for(i = 1 ; i <= n ; i ++ ) scanf("%lld" , &a2[i]) , ans += a2[i];for(i = 1 ; i <= n ; i ++ ){if(i <= k) l = 1;else l = 2 * i - 2 * k + 1;if(i > n - k) r = 2 * n - 2 * k + 3;else r = i * 2 + 1;add(l , r , 1 , a1[i] - a2[i] , i);}for(i = 2 ; i <= 2 * n - 2 * k + 2 ; i += 2)add(i , i - 1 , inf , 0 , 0) , add(i , i + 1 , inf , 0 , 0);for(i = 2 ; i <= 2 * n - 2 * k + 2 ; i ++ ){if(i & 1) add(i , t , k - t1 - t2 , 0 , 0);else add(s , i , k - t1 - t2 , 0 , 0);}add(s , 1 , t1 , 0 , 0) , add(2 * n - 2 * k + 3 , t , k - t2 , 0 , 0);printf("%lld\n" , ans + maxcost());for(i = 2 ; i <= cnt ; i ++ )if(id[i])opt[id[i]] = val[i];for(i = 1 ; i <= n ; i ++ ){if(opt[i]) printf("E");else printf("S");}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/GXZlegend/p/7883203.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj4842】[Neerc2016]Delight for a Cat 线性规划与网络流的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。