1. 餐巾计划问题
建图跑费用流即可：
- \((S,1,\inf,p)\);
- \(\forall i\in[1,N],(i,i+N,r_i,0)\);
- \(\forall i\in[1,N],(S,i+N,r_i,0)\);
- \(\forall i\in[1,N],(i,T,r_i,0)\);
- \(\forall i\in[1,N),(i,i+1,\inf,0)\);
- \(\forall i\in[1,N-n],(i+N,i+n,\inf,f)\);
- \(\forall i\in[1,N-m],(i+N,i+m,\inf,s)\);
解释一下 234：
考虑把餐巾作为流，费用作为费用。则我们需要保证最大流为 \(\sum r\)。所以每个点要拆成两部分，表示干净毛巾和脏毛巾，再用脏毛巾的点流向洗过后的干净毛巾点。
点击查看代码
//P1251
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
void solve();int main(){ solve(); return 0; }
const int N = 4e3 + 10, M = 4e4 + 10;
const ll inf = 1e10;
int n, r[N], p, u, f, v, s;
ll mc, ln[M], cs[M], ds[N];
int hd[N], eg[M], nx[M], tot = 1, nw[N], vs[N];
void adg(int u, int v, ll w, ll c){
eg[++tot] = v;
ln[tot] = w;
cs[tot] = c;
nx[tot] = hd[u];
hd[u] = tot;
}
void add(int u, int v, ll w, ll c){
// printf("%d %d %lld %lld\n", u, v, w, c);
adg(u, v, w, c);
adg(v, u, 0, -c);
}
bool spfa(int s, int t){
queue<int> q;
memset(ds, 0x3f, sizeof(ds));
memcpy(nw, hd, sizeof(hd));
q.push(s);
ds[s] = 0;
vs[s] = 1;
while(!q.empty()){
int x = q.front();
q.pop();
vs[x] = 0;
for(int i = hd[x]; i; i = nx[i]){
int y = eg[i];
ll z = ln[i], c = cs[i];
if(z && ds[y] > ds[x] + c){
ds[y] = ds[x] + c;
if(!vs[y]){
vs[y] = 1;
q.push(y);
}
}
}
}
return ds[t] != 0x3f3f3f3f3f3f3f3f;
}
ll dfs(int x, int t, ll fl){
if(x == t){
return fl;
}
ll rs = fl;
vs[x] = 1;
for(int i = nw[x]; i && rs; i = nx[i]){
int y = eg[i];
ll z = ln[i], c = cs[i];
nw[x] = i;
if(!vs[y] && z && ds[y] == ds[x] + c){
ll k = dfs(y, t, min(rs, z));
if(!k){
ds[y] = 0;
}
ln[i] -= k;
ln[i^1] += k;
rs -= k;
mc += k * c;
}
}
vs[x] = 0;
return fl - rs;
}
void solve(){
scanf("%d", &n);
for(int i = 1; i <= n; ++ i){
scanf("%d", &r[i]);
}
scanf("%d%d%d%d%d", &p, &u, &f, &v, &s);
int st = n + n + 1, ed = n + n + 2;
for(int i = 1; i <= n; ++ i){
add(i, i+n, r[i], 0);
add(st, i+n, r[i], 0);
add(i, ed, r[i], 0);
if(i < n){
add(i, i+1, inf, 0);
}
if(i + v <= n){
add(i+n, i+v, inf, s);
}
if(i + u <= n){
add(i+n, i+u, inf, f);
}
}
add(st, 1, inf, p);
while(spfa(st, ed)){
while(dfs(st, ed, inf*2));
}
printf("%lld\n", mc);
}